Search

Ensemble learning combines several individual models to obtain a better generalization performance. In this work we present a practical method for estimating the joint power of several classifiers. It differs from existing approaches which focus on "diversity" measures by not relying on labels. This makes it both accurate and practical in the modern setting of unsupervised learning with huge datasets. The heart of the method is a combinatorial bound on the number of mistakes the ensemble is likely to make. The bound can be efficiently approximated in time linear in the number of samples. We relate the bound to actual misclassifications, hence its usefulness as a predictor of performance. We demonstrate the method on popular large-scale face recognition datasets which provide a useful playground for fine-grain classification tasks using noisy data over many classes., Comment: 4 pages, 2 figures. Accepted to InfoCOG@NeurIPS 2023

The need for reliable and low-cost infrastructure is crucial in today's world. However, achieving both at the same time is often challenging. Traditionally, infrastructure networks are designed with a radial topology lacking redundancy, which makes them vulnerable to disruptions. As a result, network topologies have evolved towards a ring topology with only one redundant edge and, from there, to more complex mesh networks. However, we prove that large rings are unreliable. Our research shows that a sparse mesh network with a small number of redundant edges that follow some design rules can significantly improve reliability while remaining cost-effective. Moreover, we have identified key areas where adding redundant edges can impact network reliability the most by using the SAIDI index, which measures the expected number of consumers disconnected from the source node. These findings offer network planners a valuable tool for quickly identifying and addressing reliability issues without the need for complex simulations. Properly planned sparse mesh networks can thus provide a reliable and a cost-effective solution to modern infrastructure challenges.

We propose a hybrid model governed by the Blume-Emery-Griffiths (BEG) Hamiltonian with a mean-field-like interaction, where the spins are randomly quenched such that some of them are "pure" Ising and the others admit the BEG set of states. It is found, by varying the concentration of the Ising spins, that the model displays different phase portraits in concentration-temperature parameter space, within the canonical and the microcanonical ensembles. Phenomenological indications that these portraits are rich and rather unusual are provided., Comment: 6 pages, 4 figures

In this paper, we consider the problem of covering a plane region with unit discs. We present an improved upper bound and the first nontrivial lower bound on the number of discs needed for such a covering, depending on the area and perimeter of the region. We provide algorithms for efficient covering of convex polygonal regions using unit discs. We show that the computational complexity of the algorithms is pseudo-polynomial in the size of the input and the output. We also show that these algorithms provide a constant factor approximation of the optimal covering of the region.

A hybrid Potts model where a random concentration $p$ of the spins assume $q_0$ states and a random concentration $1-p$ of the spins assume $q>q_0$ states is introduced. It is known that when the system is homogeneous, with an integer spin number $q_0$ or $q$, it undergoes a second or a first order transition, respectively. It is argued that there is a concentration $p^\ast$ such that the transition nature of the model is changed at $p^\ast$. This idea is demonstrated analytically and by simulations for two different types of interaction: the usual square lattice nearest neighboring and mean field all-to-all. Exact expressions for the second order critical line in concentration-temperature parameter space of the mean field model together with some other related critical properties, are derived., Comment: 8 pages, 5 figures

We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random $k$-uniform hypergraph $H_{n,p;k}$, for a wide range of $p$. We also show that it is solvable w.h.p. for random $r$-regular, $k$-uniform hypergraphs $H_{n,r;k},r=O(1)$., Comment: fixed typos and added explanations

We consider optimal attacks or immunization schemes on different models of random graphs. We derive bounds for the minimum number of nodes needed to be removed from a network such that all remaining components are fragments of negligible size. We obtain bounds for different regimes of random regular graphs, Erd\H{o}s-R\'enyi random graphs, and scale free networks, some of which are tight. We show that the performance of attacks by degree is bounded away from optimality. Finally we present a polynomial time attack algorithm and prove its optimal performance in certain cases.

A combinatorial approach is used to study the critical behavior of a $q$-state Potts model with a round-the-face interaction. Using this approach it is shown that the model exhibits a first order transition for $q>3$. A second order transition is numerically detected for $q=2$. Based on these findings, it is deduced that for some two-dimensional ferromagnetic Potts models with completely local interaction, there is a changeover in the transition order at a critical integer $q_c\leq 3$. This stands in contrast to the standard two-spin interaction Potts model where the maximal integer value for which the transition is continuous is $q_c=4$. A lower bound on the first order critical temperature is additionally derived., Comment: 8 pages, 3 figures

We study the $q$ states Potts model with four site interaction on the square lattice. Based on the asymptotic behaviour of lattice animals, it is argued that when $q\leq 4$ the system exhibits a second-order phase transition, and when $q > 4$ the transition is first order. The $q=4$ model is borderline. We find ${1}/{\ln q}$ to be an upper bound on $T_c$, the exact critical temperature. Using a low-temperature expansion, we show that $1/(\theta\ln q)$, where $\theta>1$ is a $q$-dependent geometrical term, is an improved upper bound on $T_c$. In fact, our findings support $T_c=1/(\theta\ln q)$. This expression is used to estimate the finite correlation length in first-order transition systems. These results can be extended to other lattices. Our theoretical predictions are confirmed numerically by an extensive study of the four-site interaction model using the Wang-Landau entropic sampling method for $q=3,4,5$. In particular, the $q=4$ model shows an ambiguous finite-size pseudocritical behaviour., Comment: 8 pages, 6 figures

We propose an extension of the Ehrenfeucht-Fraisse game able to deal with logics augmented with Lindstrom quantifiers. We describe three different games with varying balance between simplicity and ease of use.

We study zero-one laws for random graphs. We focus on the following question that was asked by many: Given a graph property P, is there a language of graphs able to express P while obeying the zero-one law? Our results show that on the one hand there is a (regular) language able to express connectivity and k-colorability for any constant k and still obey the zero-one law. On the other hand we show that in any (semiregular) language strong enough to express Hamiltonicity one can interpret arithmetic and thus the zero-one law fails miserably. This answers a question of Blass and Harary.

We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph $G=\gc$. In this model $G$ is drawn uniformly from graphs with vertex set $[n]$, $m$ edges and minimum degree at least three. We focus on the case where $m=cn$ for constant $c$. If $c$ is sufficiently large then our algorithm runs in $O(n^{1+o(1)})$ time and succeeds w.h.p.

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of $G$ are colored. The game chromatic number \chi_g(G) is the minimum k for which the first player has a winning strategy. The paper \cite{BFS} began the analysis of the asymptotic behavior of this parameter for a random graph G_{n,p}. This paper provides some further analysis for graphs with constant average degree i.e. np=O(1) and for random regular graphs., Comment: Correction

For graphs F and G an F-matching in G is a subgraph of G consisting of pairwise vertex disjoint copies of F. The number of F-matchings in G is denoted by s(F,G). We show that for every fixed positive integer m and every fixed tree F, the probability that s(F,T_n) = 0 mod m, where T_n is a random labeled tree with n vertices, tends to one exponentially fast as n grows to infinity. A similar result is proven for induced F-matchings. This generalizes a recent result of Wagner who showed that the number of independent sets in a random labeled tree is almost surely a zero residue., Comment: 7 pages. Submitted to Electronic Journal of Combinatorics

The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial S$ denotes the set of edges with precisely one end in $S$. A random graph process on $n$ vertices, $\widetilde{G}(t)$, is a sequence of $\binom{n}{2}$ graphs, where $\widetilde{G}(0)$ is the edgeless graph on $n$ vertices, and $\widetilde{G}(t)$ is the result of adding an edge to $\widetilde{G}(t-1)$, uniformly distributed over all the missing edges. We show that in almost every graph process $i(\widetilde{G}(t))$ equals the minimal degree of $\widetilde{G}(t)$ as long as the minimal degree is $o(\log n)$. Furthermore, we show that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically $\Theta(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.