Danny Vilenchik

Starting July 2009:
Hedrick Assistant Adjunct Professor
Department of Mathematics, UCLA
Math Sciences 7911, UCLA, Los Angeles, CA 90095.

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


Email: vilenchikmath.ucla.edu

 
             Short Bio My first degree was a B.Sc. in Computer Science at the Technion, in Haifa, Israel. I completed my B.Sc. in June 2001 and went on for an M.Sc. under the advisory of Prof. Uriel Feige in the Weizmann Institute, Rehovot, Israel. Next stop was Tel-Aviv University. My doctorate was supervised by Prof. Michael Krivelevich. I submitted my PhD thesis in September 2008.

Fields of Interest

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

Papers

  1. L. Minder and D. Vilenchik.
    Small clique detection and approximate Nash equilibria.
    RANDOM 2009, LNCS     5687/2009, pages 673-685.
    [full version]

  2. U. Feige, A. Flaxman, and D. Vilenchik.
    On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas.
    submitted. [arXiv]

  3. M. Krivelevich, B. Sudakov, and D. Vilenchik.
    On the random satisfiable process.
    Combinatorics, Probability & Computing 18(5), pages 775-801. [arXiv]

  4. T. Friedrich, T. Sauerwald, and D. Vilenchik.
    Smoothed analysis of balancing networks.
    ICALP 2009, LNCS 5556/2009, pages 472-483.
    [abstract]

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

  6. A. Coja-Oghlan, E. Mossel and D. Vilenchik.
    A Spectral Approach to Analyzing Belief Propagation for 3-Coloring.
     Combinatorics Probability and Computing. To appear.
    [arXiv]

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

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

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

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

  11.  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. Also appeared in J. Theory of Computing Systems     DOI 10.1007/s00224-009-9231-5.
    [proceedings version] [jour version] [slides]

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

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

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

  15.  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. [ps]

  2. D. Vilenchik.
     A rigorous study of some satisfiability problems.
    PhD     Thesis. Tel Aviv University, 2009. [pdf]