Papers
|
-
-
M. Krivelevich,
B. Sudakov,
and D. Vilenchik.
On the random satisfiable process.
submitted. [pdf]
-
A.
Coja-Oghlan,
E.
Mossel and
D. Vilenchik. A Spectral Approach to
Analyzing Belief Propagation for 3-Coloring.
submitted. [pdf]
-
J. Böttcher
and D. Vilenchik.
On The Tractability of Coloring Semi-random Graphs. Information Processing Letters.
volume 108, issue 3, pages 143-149. [full
version]
-
D. Vilenchik.
It's
all about the support: a new perspective on the satisfiability problem.
JSAT (Journal on
Satisfiability, Boolean Modeling, and Computation), Volume 3, pages
125-139, 2007. [full version][slides]
-
A.
Coja-Oghlan,
M. Krivelevich, and D. Vilenchik.
Why almost all satisfiable
k-CNF
formulas are easy. Proceedings of the 13th International Conference on Analysis of
Algorithms, DMTCS proc., pages 89-102, 2007. [full version]
[slides]
-
S.
Ben-Shimon and D. Vilenchik. Message passing for the coloring problem:
Gallager meets Alon and
Kahale. Proceedings of the 13th International Conference on Analysis of
Algorithms, DMTCS proc., pages 217-226, 2007. [full
version]
-
A.
Coja-Oghlan,
M. Krivelevich, and D. Vilenchik.
Why almost all k-colorable graphs are
easy to color. Proceedings of the 24th International Symposium on Theoretical Aspects
of Computer Science (STACS), LNCS 4393, pages 121-132, 2007. [proceedings
version] [jour
version]
[slides]
-
U.
Feige, E.
Mossel and D. Vilenchik.
Complete convergence of
message passing algorithms for some satisfiability problems. Proceedings of Random'06, LNCS 4410, pages 339-350, 2006. [proceedings version] [full version
- TBD]
-
M.
Krivelevich, and D. Vilenchik. Solving random satisfiable 3CNF formulas in expected polynomial time. Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 454-463, 2006. [full version]
[slides]
-
M. Krivelevich, and D. Vilenchik.
Semi-Random Models as Benchmarks for Coloring
Algorithms. Proceedings of the Third Workshop on Analytic Algorithmics and
Combinatorics (ANALCO) ,
pages 211-221, 2006. [full version]
-
U.
Feige and D. Vilenchik. A
Local Search Algorithm for 3SAT.
Technical Report MCS 04-07, Computer Science and
Applied Mathematics, The Weizmann Institute of Science, 2004 [full version]
|