[math-ias] Theoretical Computer Science/Discrete Math Seminars -- Week of December 12, 2016

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of December 12, 2016


--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------

Monday, December 12

Computer Science/Discrete Mathematics Seminar I
Topic: 		On gradient complexity of measures on the discrete cube
Speaker: 	Ronen Eldan, Weizmann Institute of Science
Time/Room: 	11:15am - 12:15pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=104244



Tuesday, December 13

Computer Science/Discrete Mathematics Seminar II
Topic: 		Sum of squares lower bounds for refuting any CSP
Speaker: 	Pravesh Kothari, Member, School of Mathematics
Time/Room: 	10:30am - 12:30pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=104484

1 On gradient complexity of measures on the discrete cube
    Ronen Eldan

The motivating question for this talk is: What does a sparse Erdős–Rényi 
random graph, conditioned to have twice the number of triangles than the 
expected number, typically look like? Motivated by this question, In 
2014, Chatterjee and Dembo introduced a framework for obtaining Large 
Deviation Principles (LDP) for nonlinear functions of Bernoulli random 
variables (this followed an earlier work of Chatterjee-Varadhan which 
used limit graph theory to answer this question in the dense regime). 
The aforementioned framework relies on a notion of "low complexity" 
functions on the discrete cube, defined in terms of the covering numbers 
of their gradient. The central lemma used in their proof provides a 
method of estimating the log-normalizing constant $\log \sum_{x \in 
\{-1,1\}^n} e^{f(x)}$, which applies for functions attaining low 
complexity and some additional smoothness properties. In this talk, we 
will introduce a new notion of complexity for measures on the discrete 
cube, namely the mean-width of the gradient of the log-density. We prove 
a general structure theorem for such measures which goes beyond the 
discrete cube. In particular, we show that a measure $\nu$ attaining low 
complexity (with no extra smoothness assumptions needed) are close to a 
product measure in the following sense: there exists a measure $\tilde 
\nu$ a small "tilt" of $\nu$ in the sense that their log-densities 
differ by a linear function with small slope, such that $\tilde \nu$ is 
close to a product measure in transportation distance. An easy corollary 
of our result is a strengthening of the framework of Chatterjee-Dembo, 
which in particular simplifies the derivation of LDPs for subgraph 
counts, and improves the attained bounds.

http://www.math.ias.edu/seminars/abstract?event=104244

2 Sum of squares lower bounds for refuting any CSP
    Pravesh Kothari

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance 
of a constraint satisfaction problem (CSP(P)) where each of the $\Delta 
n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at 
random is unsatisfiable with high probability whenever the /density /of 
constraints, $\Delta \gg 1.$ The /refutation /problem asks for an 
efficient proof of unsatisfiability of such an instance that works 
correctly with high probability. We show that whenever the predicate $P$ 
fails to support a $t$-/wise-uniform/ probability distribution over its 
satisfying assignments, the Sum-of-Squares (SoS) algorithm of degree $d 
= \Theta(\frac{n}{\Delta^{2/(t-2)} \log \Delta})$ (that runs in time 
$n^{O(d)}$) /cannot /refute a random instance of CSP(P). In particular, 
polynomial time SoS algorithm requires $\sim n^{t/2}$ constraints to 
refute CSPs with predicates that support $t$-wise-uniform distribution 
on their satisying assignments. This matches the bounds known for 
special cases such as 3XOR and 3SAT [Grigoriev 2001, Schonebeck 08]. 
Together with the recent work [Lee, Raghavendra, Steurer 2015], it also 
yields that /any /polynomial-size semidefinite programming relaxation 
for refutation requires at least $\sim n^{t/2}$ constraints. More 
generally, for every constraint predicate~$P$, we get a three-way 
hardness tradeoff between the density of constraints, the SOS degree 
(hence running time), and the strength of the refutation. By recent 
known algorithmic results of [Allen, O'Donnell, Witmer 2015] and 
[Raghavendra, Rao, Schramm 2016], our full three-way tradeoff is 
/tight/, up to lower-order factors. Our results carry over to the more 
general $\delta$-refutation problem: we show that if $P$ is 
$\delta$-close to supporting a $t$-wise uniform distribution on 
satisfying assignments, then the 
degree-$\Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta})$ SoS algorithm 
cannot $(\delta+o(1))$-refute a random instance of CSP$(P)$. Our results 
also extend with no change to CSPs over larger alphabets and subsume all 
previously known lower bounds for semialgebraic refutations of random 
CSPs. They are also the first to show a distinction between the degree 
SOS needs to weakly refute random CSPs, versus $\delta$-refute them.

http://www.math.ias.edu/seminars/abstract?event=104484

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20161207/5b6a21da/attachment.html>