Teaching:

- Fal. '13 Math 4221: Stochastic Processes I
- Sp. '13 Math 6221: Advanced Classical Probability
- Fa. '12 Math 4221: Stochastic Processes I
- Sp. '12 Math 3215: Probability & Statistics
- Sp. '12 CS 8803: Discrete Fourier Analysis

Upcoming Talks:

- April 7: Paris tba.
- April 14-17: New Frontiers in Random Geometric Graphs workshop
- April 26/27: Atlanta Lecture Series in Combinatorics and Graph Theory XII
- June 18: SIAM Conference on Discrete Math: Probabilistic Combinatorics Minisymposium

On the Complexity of Random Satisfiability Problems with Planted Solutions, *preprint*, (with Vitaly Feldman and Santosh Vempala)

We consider the problem of finding a planted assignment to a random k-SAT formula (or a planted partition in a random hypergraph or a planted assignment to a general random k-CSP). This problem exhibits an algorithmic gap: while the planted solution is essentially unique with a large linear number of clauses, there are distributions for which efficient algorithms are only known for n^{k/2} clauses. We give a rigorous explanation of this gap by showing that any efficient*statistical* algorithm requires n^{r/2} clauses, where *r* is a parameter that depends on the distribution and can be as high as k. We also give a simple, iterative algorithm that matches the sample complexity up to log factors. This is concrete evidence for the security of Goldreich's proposed one-way function. Our algorithm involves a modified power iteration scheme to find a large singular value of a sparse random matrix.

We consider the problem of finding a planted assignment to a random k-SAT formula (or a planted partition in a random hypergraph or a planted assignment to a general random k-CSP). This problem exhibits an algorithmic gap: while the planted solution is essentially unique with a large linear number of clauses, there are distributions for which efficient algorithms are only known for n^{k/2} clauses. We give a rigorous explanation of this gap by showing that any efficient

Thresholds for Random Geometric k-SAT, *preprint*, (with Milan Bradonjic) slides from RSA 2013

We consider a geometric version of random k-SAT: literals are placed uniformly at random in a cube and a k-clause formed for every set of k literals in a ball of radius r. We find the satisfiability threshold for k=2, and show that the threshold is sharp for all k in a Poissonized model.

We consider a geometric version of random k-SAT: literals are placed uniformly at random in a cube and a k-clause formed for every set of k literals in a ball of radius r. We find the satisfiability threshold for k=2, and show that the threshold is sharp for all k in a Poissonized model.

Computer-enabled Metrics of Statistical Significance for Discrete Data, *preprint*, (with Mark Tygert and Rachel Ward)

This monograph addresses basic problems in statistical significance from an algorithmic perspective. We show that a simple root-mean-square test and the discrete Kolmogorov-Smirnov test are often superior to classical chi-square statistics, and give the relevant theory along with numerous examples.

This monograph addresses basic problems in statistical significance from an algorithmic perspective. We show that a simple root-mean-square test and the discrete Kolmogorov-Smirnov test are often superior to classical chi-square statistics, and give the relevant theory along with numerous examples.

Random k-SAT and the Power of Two Choices, *to appear, Random Structures and Algorithms*. slides

I give an Achlioptas rule to shift the satisfiability threshold for random k-SAT. Previously this was known for k=2 (Sinclair/Vilenchik), and the parameters have since been improved (Dani et al). I also propose a semi-random decision problem for random k-SAT.

I give an Achlioptas rule to shift the satisfiability threshold for random k-SAT. Previously this was known for k=2 (Sinclair/Vilenchik), and the parameters have since been improved (Dani et al). I also propose a semi-random decision problem for random k-SAT.

Some deficiencies of χ^{2} and classical exact tests of significance, *Applied and Computational Harmonic Analysis*, to appear. (with Mark Tygert and Rachel Ward)

We indicate the serious problems faced by the chi-square test in dealing with sparse data and propose a remedy. See Andrew Gellman's blog post for a discussion.

We indicate the serious problems faced by the chi-square test in dealing with sparse data and propose a remedy. See Andrew Gellman's blog post for a discussion.

On the Resilience of Bipartite Networks, *submitted*, (with Lev Reyzin)

We study the question `Which networks are least susceptible to widespread infection?' asked in (Blume et al) for d-regular graphs. Here we consider half-regular bipartite graphs, a natural model in many applications, and give extremal results, worst-case NP-hardness, and draw a connection with the study of percolation on finite graphs.

We study the question `Which networks are least susceptible to widespread infection?' asked in (Blume et al) for d-regular graphs. Here we consider half-regular bipartite graphs, a natural model in many applications, and give extremal results, worst-case NP-hardness, and draw a connection with the study of percolation on finite graphs.

Large Deviations for the Empirical Distribution in the Branching Random Walk, *submitted*, (with Oren Louidor)

We consider large deviations in the empirical distribution of a super-critical branching random walk. In particular we answer questions such as: What is the asymptotic probability that at least 70% of particles are between -Sqrt(n) and Sqrt(n) after n steps, instead of the expected 68%? We find there are two distinct regimes if the set considered is a finite union of intervals, with rates interpolating between the two for sets that are countable unions of intervals.

We consider large deviations in the empirical distribution of a super-critical branching random walk. In particular we answer questions such as: What is the asymptotic probability that at least 70% of particles are between -Sqrt(n) and Sqrt(n) after n steps, instead of the expected 68%? We find there are two distinct regimes if the set considered is a finite union of intervals, with rates interpolating between the two for sets that are countable unions of intervals.

The Bohman-Frieze Process Near Criticality (with Mihyun Kang and Joel Spencer), * Random Structures and Algorithms*, 2013. slides

We study the fine behavior of the phase transition of the Bohman-Frieze random graph process, and show that it shares several critical exponents with the Erdos-Renyi random graph. Our technique involves deriving a PDE associated to the process and using singularity analysis to extra information about small components from a multivariate generating function.

We study the fine behavior of the phase transition of the Bohman-Frieze random graph process, and show that it shares several critical exponents with the Erdos-Renyi random graph. Our technique involves deriving a PDE associated to the process and using singularity analysis to extra information about small components from a multivariate generating function.

Hardness of Finding Independent Sets In Almost 3-Colorable Graphs, * FOCS * 2010 (with Irit Dinur, Subhash Khot, and Muli Safra) slides

With techniques adapted from (Dinur/Safra) and Fourier analysis on the discrete q-ary hypercube, we prove hardness of approximation for graph coloring. In particular, we show that it is NP-hard to distinguish a graph that is almost k-colorable from one whose largest independent set is a 1/k^2 fraction of the graph.

With techniques adapted from (Dinur/Safra) and Fourier analysis on the discrete q-ary hypercube, we prove hardness of approximation for graph coloring. In particular, we show that it is NP-hard to distinguish a graph that is almost k-colorable from one whose largest independent set is a 1/k^2 fraction of the graph.

The Forgetfulness of Balls and Bins, * Random Structures and Algorithms*, 2012. slides

I answer the question 'How many additional random balls are necessary to disguise an arbitrary initial placement of m balls in n bins?' with a precise answer that depends on the empirical variance of the initial placement.

I answer the question 'How many additional random balls are necessary to disguise an arbitrary initial placement of m balls in n bins?' with a precise answer that depends on the empirical variance of the initial placement.

Computing the confidence levels for a root-mean-square test of goodness-of-fit, * Applied Mathematics and Computation*, 2011 (with Mark Tygert and Rachel Ward)

We give an efficient numerical algorithm for computing the asymptotic distribution of a root-mean-square goodness of fit test. The algorithm is a numerical evaluation of a contour integral.

We give an efficient numerical algorithm for computing the asymptotic distribution of a root-mean-square goodness of fit test. The algorithm is a numerical evaluation of a contour integral.