8 citations · 9 across the 9 of their papers we have counts for
9 papers
A computational method for bounding the probability of reconstruction on trees
Nayantara Bhatnagar, Elitza Maneva
For a tree Markov random field non-reconstruction is said to hold if as the depth of the tree goes to infinity the information that a typical configuration at the leaves gives abou…
On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
Elitza Maneva, Alistair Sinclair
We study the structure of satisfying assignments of a random 3-SAT formula. In particular, we show that a random formula of density 4.453 or higher almost surely has no non-trivial…
Pruning Processes and a New Characterization of Convex Geometries
Federico Ardila, Elitza Maneva
We provide a new characterization of convex geometries via a multivariate version of an identity that was originally proved by Maneva, Mossel and Wainwright for certain combinatori…
A Hike in the Phases of the 1-in-3 Satisfiability
Elitza Maneva, Talya Meltzer, Jack Raymond +2
We summarise our results for the random --1-in-3 satisfiability problem, where is a probability of negation of the variable. We employ both rigorous and heuristic methods to…
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva +1
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisf…
New model for rigorous analysis of LT-codes
Elitza N. Maneva, Amin Shokrollahi
We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the firs…