Near log-convexity of measured heat in (discrete) time and consequences
1:00 PM to 2:00 PM
CS conference room (CSB 453)
Mert Saglam, University of Washington
We answer a 1982 conjecture of Erdos and Simonovits about the growth of number of k-walks in a graph, which incidentally was posed as a question earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of the k-Hamming distance is Omega(k log k) and that consequently any property tester for k-linearity requires Omega(k log k) queries.
Add to GMail
Hardness of certification for random optimization problems
1:00 PM to 2:00 PM
CS conference room (CSB 453)
Tim Kunisky, New York University
Certifying bounds on random optimization problems is an important computational task arising in many settings, from bounding the number of constraints of a random SAT instance that can be satisfied to controlling the size of an extremal structure in a random graph. It is usually quite difficult, however, to prove for families of certification algorithms like linear or semidefinite programs that they fail to optimize a random objective past a certain value. I will describe a recent work in which we produce a reduction from the task of certifying bounds on random quadratic programs to the task of hypothesis testing in a statistical model. We then apply a recently-developed heuristic connecting low-degree polynomial approximations of the likelihood ratio to the hardness of hypothesis testing, which gives strong evidence for the hardness of certification for a large class of random quadratic programs. Interpreted geometrically, our work suggests a gap between the mean width of certain convex sets of matrices, such as the cut polytope, and the mean width of any computationally tractable convex relaxation thereof.
Based on joint work with Afonso Bandeira and Alex Wein.
Add to GMail