Danny Vilenchik

Starting September 2011:
Postodoc
Facutly of Mathematics & Computer Science, The Weizamnn Institute.
Rehovot, Israel.

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


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

C. Lee, B. Sudakov, and D. Vilenchik.
Getting directed Hamilton cycle twice faster.
submitted. [arXiv]

I. Pak and D. Vilenchik.
Constructing Uniquely Realizable Graphs.
submitted.
[full version]

A. Sinclair and D. Vilenchik.
Delaying satisfiability for random 2SAT.
Proceedings of RANDOM 2010, pages 710-723.
[full version]

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

U. Feige, A. Flaxman, and D. Vilenchik.
On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas.
SIAM Journal on Discrete Mathematics 25(2), pages 736-749, 2011 [journal version]

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

T. Friedrich, T. Sauerwald, and D. Vilenchik.
Smoothed analysis of balancing networks.
Random Structures & Algorithms 39(1), pages 115-138, 2011 (Proceedings version appeared in ICALP 2009).
[abstract][journal version]

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]

A. Coja-Oghlan, E. Mossel and D. Vilenchik.
A Spectral Approach to Analyzing Belief Propagation for 3-Coloring.
 Combinatorics Probability and Computing, volume 108, issue 3, pages 881-912, 2009.
[arXiv]

J. Böttcher and D. Vilenchik.
On The Tractability of Coloring Semi-random Graphs.
Information Processing Letters. volume 108, issue 3, pages 143-149, 2008.
[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. Also appeared in J. Theory of Computing Systems, volume 46, issue 3, pages 523-565, 2009.
[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]

 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]

Manuscripts

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

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