Danny Vilenchik

Starting August 2008:
Computer Science Division, University of California Berkeley.
Host: Prof. Alistair Sinclair

Ph.D. student (advisor: Prof. Michael Krivelevich)
School of Computer Sciences
Tel-Aviv University
Ramat Aviv, Tel-Aviv 69978
Office: 03-6405398
Email: vilenchipost.tau.ac.il

 

 
             Short CV

I got my B.Sc in computer science from the Technion (1998),

and did my M.Sc in computer science at the Weizmann Institute under the supervision of Prof. Uriel Feige (2004).

[full cv]

Fields of Interest

Probabilistic methods in combinatorics, random structures and average case analysis (in particular, k-SAT and k-colorability).

Papers

  1. A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, and D. Vilenchik.
    On smoothed k-CNF formulas and the Walksat algorithm.
    SODA 2009, to appear.
    [full version]

  2. M. Krivelevich, B. Sudakov, and D. Vilenchik.
    On the random satisfiable process. submitted.
    [pdf]

  3. A. Coja-Oghlan, E. Mossel and D. Vilenchik.
    A Spectral Approach to Analyzing Belief Propagation for 3-Coloring. submitted.
    [pdf]

  4. 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]

  5. 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]

  6. 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]

  7.  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]

  8.  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]

  9.  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]

  10.  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]

  11. 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]

  12.  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]

Manuscripts

  1. D. Vilenchik.
    Finding a satisfying assignment for semi-random satisfiable 3CNF formulas
    Master Thesis. The Weizmann Institute of Science, 2004
    [full version]