Transcript The probabilistic method New frontiers and challenges

The probabilistic method:
New frontiers and old challenges
Shachar Lovett (UCSD)
ELC Tokyo Complexity Workshop,
March 2013
The probabilistic method
• Non-constructive way to prove existence of
mathematical objects
• Pioneered by Erdös in combinatorics
• Numerous applications in theoretical
computer science, combinatorics, number
theory, analysis, geometry,…
The probabilistic method
• Recipe: to prove existence of an object with certain
prescribed properties,
1. Define a distribution on the objects
2. Sample an object
3. Prove that with positive probability the object
sampled has the required properties
 The required objects must exist !
Example: bad movies
• How to find a bad movie… pick one at random!
Photo courtesy of
elijahconsulting.com
Example: good codes
• Binary code: subset C of {0,1}n (codewords)
• Code is good if there are constants ,>0 s.t
– |C| 2n (good rate)
– Two codewords differ in at least n coordinates
(good distance)
• Claim: good codes exist (for suitable ,)
• In fact, they are abundant
Example: good codes
CODEWORD
MINIMAL DISTANCE
AROUND CODEWORD
Example: good codes
• Good code: C{0,1}n, |C|=2n, min dist  n
• Distribution: uniform over subsets of size 2n
• Probability that the code contains two elements
of hamming distance n is approximately
2𝛼𝑛
2
𝑛
−𝑛
2
≤ 𝛽𝑛
• Exponentially small if , are small enough
Example: good codes
• Almost all codes are good
• This, however, tells us very little on how to
find good codes (of course, we can randomly
sample them and hope for the best)
• Even more, it tells us nothing on how to build
efficient algorithms for encoding, decoding, …
Archetypical setup
• In most cases, the probabilistic method shows
that not only the required objects exist, but in
fact they are abundant
– Most codes are good, most sparse graphs are
expanders, most functions are hard to compute,
most matrices are rigid, …
• Challenge: find explicit objects
– Major line of research in TCS, number theory,
geometry, combinatorics, …
Rare objects
• There are quite a few cases, however, when the standard
application of the probabilistic method fails miserably
• This is simply because the required objects may exist, but
they are certainly not abundant
• Looking for few (if any) needles in very large haystacks…
Photo courtesy of
footprinthr.com.au
Rare objects
• Solutions?
• Explicit constructions: great, when we have them.
This is the ultimate goal. But, in many cases we
don’t have any.
• More delicate probabilistic techniques: the focus
of this talk.
– Potential for new algorithmic tools
Probabilistic techniques for rare objects
1. Limited independence: Lovász local lemma
2. Discrepancy problems: Spencer’s “six
standard deviations suffice” theorem
3. Regular structures: approximation of discrete
processes by continuous processes
Probabilistic techniques for rare objects
1. Limited independence: Lovász local lemma
2. Discrepancy problems: Spencer’s “six
standard deviations suffice” theorem
3. Regular structures: approximation of discrete
processes by continuous processes
Lovász local lemma
[Lovász-Erdös ‘75, Spencer ’77, Shearer ’85]
• Powerful tool to analyze events which are mostly
independent
• Typical application:
– E1,…,En “bad” events
– Each Ei depends on at most d other events
– Prob[Ei]  1/ed
(e=2.718…)
Thm: It is possible that none of the events occur
Lovász local lemma
• Example: G is d-regular graph on n vertices
• Color vertices with {-1,+1}
• Goal: minimize absolute sum of neighbors for
the worst vertex
• Think of n >> d, say n=exp(d)
• What is the best we can hope for?
Lovász local lemma
• d-regular graph, color vertices {-1,+1},
minimize absolute sum of neighbors
Lovász local lemma
• d-regular graph, color vertices {-1,+1},
minimize absolute sum of neighbors
-
+
+
-
-
+
+
+
-
+
+
Lovász local lemma
• d-regular graph, color vertices {-1,+1},
minimize absolute sum of neighbors
-
abs sum: 3
+
+
-
-
+
+
+
-
+
+
Lovász local lemma
• d-regular graph, color vertices {-1,+1}, minimize
absolute sum of neighbors
• Naïve bound: d
• Random assignment: w.h.p also d if n>>exp(d)
• Lovász local lemma: can get O( d log(d ))
– That is, there are “rare” colorings which are much
better than typical colorings
• Beck-Fiala conjecture (special case): can get O( d )
Lovász local lemma
• d-regular graph, color vertices {-1,+1}, minimize
absolute sum of neighbors
• Theorem: exist coloring with abs sum 𝑂
𝑑 𝑙𝑜𝑔 𝑑
• Proof: Consider a random coloring
– “Bad” event Ei: Vertex i has abs neighbors sum ≥
𝑂 𝑑 𝑙𝑜𝑔 𝑑
– Graph has degree d  Pr[Ei]  O(1/d2)
– Each event depends on ≤d2 other events
– LLL: There exists a coloring where no Ei occurs
Lovász local lemma
[Moser ‘08, Moser-Tardos ’09, Kolipaka-Szegedy’ 11]
• Constructive version: find a feasible solution where
none of the bad events holds
• Can be done!
• Algorithm (for our example): Start with a random
coloring; If a vertex has too large abs sum of neighbors,
resample his neighbors. Repeat.
• Amazingly, converges to feasible solution in poly-time!!!
Probabilistic techniques for rare objects
1. Limited independence: Lovász local lemma
2. Discrepancy problems: Spencer’s “six
standard deviations suffice” theorem
3. Regular structures: approximation of discrete
processes by continuous processes
Discrepancy problems
• Elements: 1,2,….,n
• Sets: S1,…,Sm  {1,…,n}
• Goal: Color each element {-1,+1} to minimize
absolute sum (discrepancy) in worst case set
• For example, the graph problem we saw before is
an instance of discrepancy problems
– Sets = neighbors of vertices
• A general framework
Discrepancy in geometry
• Example:
– n points in Rd (think of d as constant)
– Color them so that each half-space is balanced
• Random coloring: discrepancy O
• True answer: 𝑂𝑑 𝑛
1
1
−
2
2𝑑
[Alexander’90, Matoušek ’95]
𝑛 log 𝑛
Discrepancy in number theory
• Example:
– Color {1,…,n} so that each arithmetic progression (e.g.
{a,a+d,a+2d,…,a+kd}) is balanced
• Random coloring: discrepancy O( n log(n))
• True answer: O(n1/4 )
[Roth’64, Matoušek-Spencer ’96]
• Conjecture of Erdös: for homogeneous arithmetic
progressions (e.g. {0,d,2d,…,kd}) the answer is O(1)
– Best known is O(log n)
Discrepancy problems
• What is the best bound if no prior knowledge
is assumed on the structure of the sets?
• [Spencer ’85]: for any family of n elements
and m sets there exists a coloring with
discrepancy O( n log(m / n))
– Beats the O( n log(m)) for random colorings
– For m=n gets 6 n
– Previously mentioned results use the same proof
technique + domain specific knowledge
Algorithmic discrepancy theory
[Bansal ‘10, L-Meka’12]
• Constructive version: find a coloring with good
discrepancy
• Can be done!
• Bansal algorithm: SDP relaxation + clever rounding
• L-Meka algorithm: Random walk on fractional colorings
Some applications of algorithmic
discrepancy theory
• Phase transition for random integer programs
[Chandrasekaran-Vempala’12]
• Improved approximation algorithm for binpacking [Rothvoss’13]
• Codes with bounded peak-to-mean envelope
[Work in progress with Kotzer, Litsyn]
Open problems in discrepancy
• Beck-Fiala theorem: if any element belongs to d sets,
then the discrepancy is < 2d
• Beck-Fiala conjecture: true answer is 𝑂
– Best non-constructive bound: 𝑂
𝑑
𝑑 log 𝑛 [Banaszczyk’97]
– Best constructive bound: 𝑂 𝑑 log 𝑛
– Special case of yet another conjecture (Komlos conjecture)
• Constructive versions of the domain specific
applications of Spencer’s theorem
Probabilistic techniques for rare objects
1. Limited independence: Lovász local lemma
2. Discrepancy problems: Spencer’s “six
standard deviations suffice” theorem
3. Regular structures: approximation of discrete
processes by continuous processes
Regular structures
• Combinatorial structures with regular
symmetric structure
• Examples:
– Regular graphs
– Designs
– K-wise permutations
Regular graphs
• Graph is d-regular if all vertices have degree d
• Easy to construct, many examples
• Not so easy to count
• E.g. what is the probability that a random graph
is d-regular?
Designs
• Design = regular hypergraph
• t-(n,k,) design: k-uniform hypergraph on n
vertices, where each t elements are in exactly
 edges
• d-regular graph: 1-(n,2,d) design
Designs
• t-(n,k,) design: k-uniform hypergraph, where each t
elements are in exactly  edges
• Not so easy to construct anymore
• Algebraic constructions for small parameters
– e.g. 5-(24,8,1) design
• [Teirlinck’87] Recursive combinatorial construction for
all t; k=t+1; and n,  satisfying some modular conditions
– Few other asymptotic constructions for sparse parameters
Designs
• t-(n,k,) design: k-uniform hypergraph, where each t
elements are in exactly  edges
• Existence unknown for almost all parameters
• Open problem: Steiner systems
– t-(n,k,1) designs
– Known for t5
• Open problem: Hadamard matrices
– 2-(4n-1,2n-1,n-1) designs
– Known in special cases, e.g. n=2m
K-wise permutations
• Sn = group of permutations on n elements
• Family F  Sn is k-wise independent if its action
on k-tuples is uniform, that is if
𝜋 ∈ 𝐹: 𝜋 𝑖1 = 𝑗1 , … , 𝜋 𝑖𝑘 = 𝑗𝑘
for all distinct i1,…,ik and j1,…,jk
𝑛−𝑘 !
=
|𝐹|
𝑛!
K-wise permutations
• Trivial solution: all permutations (e.g. n!)
• Explicit algebraic constructions of polynomial size
(e.g 𝑛𝑂 𝑘 ) are known only for k=1,2,3
– Based on group symmetries
– Provably fail for k>3 and n>24
• Explicit combinatorial constructions of
exponential size (e.g 𝑘 𝑂 𝑛 )
[Finucane-Peled-Yaari’12]
Common scenarios
• Very regular objects
• Explicit constructions known in few cases, if
any
• When constructions are unknown, so is
existence…
Why not use the probabilistic method?
• If we don’t know how to construct regular
objects explicitly, why not prove existence by
the probabilistic method?
• Lets take as a case study the problem of dregular graphs (and forget for a minute that
we know how to construct them explicitly)
Probabilistically constructing
d-regular graphs
• G random graph on n vertices, each edge is
independently chosen with probability 𝑝 =
𝑑
𝑛−1
• Expected degree of a vertex = d
• What is the probability that all vertices have
exactly degree d?
• Main problem: correlation
Probabilistically constructing
d-regular graphs
• G random graph on n vertices, each edge is
independently chosen with probability 𝑝 =
• Random variables X1,…,Xn:
– Xi = degree of vertex i
• They are all dependent!
• Eliminates method which apply limited
dependence, like the Lovász local lemma
𝑑
𝑛−1
Probabilistically constructing
d-regular graphs
• G random graph on n vertices, each edge is
independently chosen with probability 𝑝 =
𝑑
𝑛−1
• [Mckay-Wormald’90] Joint distribution of degrees
(which is discrete) can be approximated by a
Gaussian distribution (if d is large enough)
• Allows to approximately count d-regular graphs
(up to 1+o(1) terms, for large enough d)
Probabilistically constructing
regular structures
• [Kuperberg-L-Peled’12] General technique for
approximation discrete distributions by
Gaussian distributions
• Allows to prove existence (and count)
– Designs for (nearly) all underlying parameters
– K-wise permutations
• Main tools: Fourier analysis, coding theory
Open problems is regular objects
• More applications
– q-analogs (vector field analog of designs) [Fazeli, Vardy]
– Conjectures in group theory
• Make it algorithmic
– Even special cases will be very interesting, e.g. finding
4-wise permutations
– Given the state of affairs for the Lovász local lemma
and Spencer’s theorem, we are hopeful…
Facing the future
• Many potential applications for techniques which
prove existence of rare combinatorial structures
• In principal, might give efficient algorithms to
problems with exponential solution space
• Some examples:
– Hadamard matrices and other “tight” structures
– Graph problems with disallowed minors
– Local codes
Tight structures
• Some of the famous open problems in
combinatorics are on “tight” structures
• Example: Hadamard matrices
–
–
–
–
–
Orthogonal 𝑛 × 𝑛 matrices with {-1,1} entries
Can only exist if n=4m
Equivalent to 2-(4m-1,2m-1,m-1) designs
Several algebraic constructions
Conjecture: exist for any n=4m
• Why not use probabilistic techniques to prove
existence?
Graphs with disallowed minors
• Probabilistic techniques are widely used in
graph theory, but they don’t always work
• Example: Zarankiewicz problem
– How many edges can a bipartite (n,n) graph have
without having a complete Kk,k sub-graph?
– Only constructions which match lower bounds are
algebraic, for k=1,2,3
– Probabilistic techniques all fail (so far)
Local codes
• Error correcting codes allow to detect and
correct errors
• Typically require the receiver to read the
entire codeword
• A code is local if some operations can be done
locally, while only reading a small part of the
received codeword
Local codes
• Many variants
• Locally testable codes are at the combinatorial
core of many PCP theorems
• Locally decodable codes are related to Private
Information Retrievel (PIR) schemes
• Locally correctable codes are related to matrix
rigidity and arithmetic circuits lower bounds
Local codes
• Many constructions: combinatorial and
algebraic
• Large gaps between lower and upper bounds
• No probabilistic constructions (so far) – can
potentially dramatically improve upper bounds
Summary
• The probabilistic method is a powerful tool with
applications in many fields
• Mathematical extensions of the probabilistic
method can show existence of very interesting
objects
• Algorithmic analogs can yield new types of
algorithms, which find “rare” solutions efficiently
Rare events…
Photo courtesy of
personal.vu.nl/h.c.tijms
THANK YOU!