Will Perkins

Georgia Tech

  • perkins@math.gatech.edu
  • office: Skiles 017
  • CV pdf
Upcoming Talks:

Research

I'm an NSF postdoc at Georgia Tech hosted by Prasad Tetali. Before that I got my PhD at NYU with Joel Spencer. My research is a combination of probability, algorithms, phase transitions and statistics. In particular, I study sparse random structures and sparse data, and associated probabilistic and algorithmic questions.

    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
Georgia Tech's robot