• 0102 computer and information sciences close

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters $\beta$ (the interaction) and $\lambda$ (the external field), except for the case $\vert{\lambda}\vert=1$ (the "zero-field" case). A randomized algorithm (FPRAS) for all graphs, and all $\beta,\lambda$, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the "decay of correlations" property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher. Comment: clarified presentation of combinatorial arguments, added new results on optimality of univariate Lee-Yang theorems

International audience; In this paper, we show how to compute an over-approximation for the reachable set of uncertain nonlinear continuous dynamical systems by using guaranteed set integration. We introduce two ways to do so. The first one is a full interval method which handles whole domains for set computation and relies on state-of-the-art validated numerical integration methods. The second one relies on comparison theorems for differential inequalities in order to bracket the uncertain dynamics between two dynamical systems where there is no uncertainty. Since the derived bracketing systems are piecewise Ck-differentiable functions, validated numerical integration methods cannot be used directly. Hence, our contribution resides in the use of hybrid automata to model the bounding systems. We give a rule for building these automata and we show how to run them and address mode switching in a guaranteed way in order to compute the over approximation for the reachable set. The computational cost of our method is also analyzed and shown to be smaller that the one of classical interval techniques. Sufficient conditions are given which ensure the epsiv-practical stability of the enclosures given by our hybrid bounding method. Two examples are also given which show that the performance of our method is very promising.

Abstract Yao's millionaire protocol enables Alice and Bob to know whether or not Bob is richer than Alice by using a public-key cryptosystem without revealing the actual amounts of their properties. In this paper, we present simple and practical implementations of Yao's millionaire protocol using a physical deck of playing cards; we straightforwardly implement the idea behind Yao's millionaire protocol so that even non-experts can easily understand their correctness and secrecy. Our implementations are based partially on the previous card-based scheme proposed by Nakai, Tokushige, Misawa, Iwamoto, and Ohta; their scheme admits players' private actions on a sequence of cards called Private Permutation (PP), implying that a malicious player could make an active attack (for example, he/she could exchange some of the cards stealthily when doing such a private action). By contrast, our implementations rely on a familiar shuffling operation called a random cut, and hence, they can be conducted completely publicly so as to avoid any active attack. More specifically, we present two card-based implementations of Yao's millionaire protocol; one uses a two-colored deck of cards (which consists of black and red cards), and the other uses a standard deck of playing cards. Furthermore, we also provide card-based protocols that rely on a logical circuit representing the comparison.

Motivated by conversations with operators and by possibilities to unlock future Internet-based applications, we study how to enable Internet Service Providers (ISPs) to reliably offer connectivity through disjoint paths as an advanced, value-added service. As ISPs are increasingly deploying Segment Routing (SR), we focus on implementing such service with SR. We introduce the concept of robustly disjoint paths, pairs of paths that are constructed to remain disjoint even after an input set of failures, with no external intervention (e.g., configuration change). We extend the routing theory, study the problem complexity, and design efficient algorithms to automatically compute SR-based robustly disjoint paths. Our algorithms enable a fully automated approach to offer the disjoint-path connectivity, based on configuration synthesis. Our evaluation on real topologies shows that such an approach is practical, and scales to large ISP networks.

We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the \(\ell _p\)-norm of the vector of loads of the machines, and each case allow the possibility of job rejection.

We motivate and give semantics to theory presentation combinators as the foundational building blocks for a scalable library of theories. The key observation is that the category of contexts and fibered categories are the ideal theoretical tools for this purpose.

A $(t, s, v)$-all-or-nothing transform is a bijective mapping defined on $s$-tuples over an alphabet of size $v$, which satisfies the condition that the values of any $t$ input co-ordinates are completely undetermined, given only the values of any $s-t$ output co-ordinates. The main question we address in this paper is: for which choices of parameters does a $(t, s, v)$-all-or-nothing transform (AONT) exist? More specifically, if we fix $t$ and $v$, we want to determine the maximum integer $s$ such that a $(t, s, v)$-AONT exists. We mainly concentrate on the case $t=2$ for arbitrary values of $v$, where we obtain various necessary as well as sufficient conditions for existence of these objects. We consider both linear and general (linear or nonlinear) AONT. We also show some connections between AONT, orthogonal arrays and resilient functions. Comment: 13 pages

Diestel and Leader have characterised connected graphs that admit a normal spanning tree via two classes of forbidden minors. One class are Halin's $(\aleph_0,\aleph_1)$-graphs: bipartite graphs with bipartition $(\mathbb{N},B)$ such that $B$ is uncountable and every vertex of $B$ has infinite degree. Our main result is that under Martin's Axiom and the failure of the Continuum Hypothesis, the class of forbidden $(\aleph_0,\aleph_1)$-graphs in Diestel and Leader's result can be replaced by one single instance of such a graph. Under CH, however, the class of $(\aleph_0,\aleph_1)$-graphs contains minor-incomparable elements, namely graphs of binary type, and $\mathcal{U}$-indivisible graphs. Assuming CH, Diestel and Leader asked whether every $(\aleph_0,\aleph_1)$-graph has an $(\aleph_0,\aleph_1)$-minor that is either indivisible or of binary type, and whether any two $\mathcal{U}$-indivisible graphs are necessarily minors of each other. For both questions, we construct examples showing that the answer is in the negative. Comment: 21 pages

We present a new set of generators for unitary maps over ${\mathbb{C}}^{2}$ which differs from the traditional rotation-based generating set in that it uses a single-parameter family of unitaries $J(\ensuremath{\alpha})$. These generators are implementable in the one-way model [Raussendorf and Briegel, Phys. Rev. Lett. 86, 5188 (2001)] using only two qubits, and lead to both parsimonious and robust implementations of general unitaries. As an illustration, we give an implementation of the controlled-$U$ family which uses only 14 qubits, and has a 2-colorable underlying entanglement graph (known to yield robust entangled states).

International audience; Data Mashup is a special class of applications mashup thatcombines data elements from multiple data sources (that are often ex-ported as data web services) to respond to transient business needs onthe y. In this paper, we propose a semantic model for data servicesalong with a declarative approach for creating data mashups withoutany programming involved. Given a query formulated over domain on-tologies, and a set of preferences modeled using the fuzzy set theory,our approach selects the relevant data services based on their semanticmodeling using an RDF query rewriting algorithm. Selected services arethen orchestrated using a ranking-aware algebra to rank their returnedresults based on users preferences at the data mashup execution time.