Zobrazeno 1 - 10
of 17
pro vyhledávání: '"Elitza Maneva"'
Autor:
Albert Atserias, Elitza Maneva
Publikováno v:
Recercat. Dipósit de la Recerca de Catalunya
instname
instname
We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::60d35e923d748eaea705c53418ae9d4b
https://doi.org/10.1016/j.ic.2011.01.003
https://doi.org/10.1016/j.ic.2011.01.003
Autor:
Elitza Maneva, Nayantara Bhatnagar
Publikováno v:
SIAM Journal on Discrete Mathematics. 25:854-871
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 about the value at the root goes to zero. The distribution of the measure
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bee1cf229372cc3082f9b460bc75b255
https://doi.org/10.1137/090751244
https://doi.org/10.1137/090751244
Publikováno v:
IEEE Transactions on Information Theory. 56:1351-1368
We study the use of low-density generator matrix (LDGM) codes for lossy compression of the Bernoulli symmetric source. First, we establish rigorous upper bounds on the average distortion achieved by check-regular ensemble of LDGM codes under optimal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8456c1eb5a6947963e336eb1201c1b15
https://doi.org/10.1109/tit.2009.2039160
https://doi.org/10.1109/tit.2009.2039160
Autor:
Elitza Maneva, Federico Ardila
Publikováno v:
Discrete Mathematics. 309(10):3083-3091
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 combinatorial objects arising in the context of the k-SAT problem. We thus highli
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4e89a90a46498b4c73ec4fcc50374759
Autor:
Alistair Sinclair, Elitza Maneva
Publikováno v:
Theoretical Computer Science. 407:359-369
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 almost surely has no non-trivial “core” assignments. Core assignments are certain partial assignments t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::281be5f1541a8b997fe80fdc38185f1c
https://doi.org/10.1016/j.tcs.2008.06.053
https://doi.org/10.1016/j.tcs.2008.06.053
Autor:
Elitza Maneva, Albert Atserias
Publikováno v:
Dipòsit Digital de la UB
Universidad de Barcelona
Recercat. Dipósit de la Recerca de Catalunya
instname
ITCS
Universidad de Barcelona
Recercat. Dipósit de la Recerca de Catalunya
instname
ITCS
Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\math
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4cde3e2b852d56f7b0a8895764f25136
http://hdl.handle.net/2445/33855
http://hdl.handle.net/2445/33855
Autor:
Albert Atserias, Elitza Maneva
Publikováno v:
Automata, Languages and Programming ISBN: 9783642141645
ICALP (1)
ICALP (1)
We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::649affb086fcb4d7adf76f8fde37a6b4
https://doi.org/10.1007/978-3-642-14165-2_10
https://doi.org/10.1007/978-3-642-14165-2_10
Publisher Summary This chapter discusses the hike in the phases of the 1-in-3 satisfiability. 1-in-3 SAT is a boolean satisfaction problem. Each formula consists of a set of variables and clauses, and each clause contains 3 literals. A clause is sati
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::399ea7fbf4552dc6455f736768e76fb4
https://doi.org/10.1016/s0924-8099(07)80022-9
https://doi.org/10.1016/s0924-8099(07)80022-9
Autor:
Elitza Maneva, Amin Shokrollahi
Publikováno v:
ISIT
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 first rigorous expression for the limiting bit-error probability as the le
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aebcb41c9bd50f7df6da98f34745be7e
https://doi.org/10.1109/isit.2006.262139
https://doi.org/10.1109/isit.2006.262139
Publikováno v:
Automata, Languages and Programming ISBN: 9783540359043
ICALP (1)
ICALP (1)
Given a Boolean formula, do its solutions form a connected subgraph of the hypercube? This and other related connectivity considerations underlie recent work on random Boolean satisfiability. We study connectivity properties of the space of solutions
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e332b2aec0bc488aa5cc33f4ad6c50e7
https://doi.org/10.1007/11786986_31
https://doi.org/10.1007/11786986_31