Transcript Document

Power and Limitations of Local Algorithms for
Network Optimization Problems
David Gamarnik
MIT
Asymptotics of Large-Scale Interacting Networks
Banff
February, 2013
Outline
I.
Who is in interested in local algorithms.
II. Success stories.
III. Random graphs. Structural results
IV. Geometry of solution space in random graphs
V. Local algorithms for random graphs. I.I.D factors.
Hatami, Lovasz & Szegedy conjecture. Negative results.
Local Algorithms
I. Who is interested in local algorithms?
Computer Science. Distributed algorithms.
Applications: hardware, fault-tolerant models of computation,
sensor networks.
Lynch (book) [1996], Suomela (survey) [2011]
Electrical Engineering.
Applications: signal processing, communications theory, wireless
communication, message passing algorithms, gossip algorithms.
Wainwright & Jordan [2008], Mezard & Montanari [2009], Shah [2008],
I. Who is interested in local algorithms?
Network Economics and Sociology.
Applications: consensus, price formation.
Jackson [2010], Judd, Kearns & Vorobeychik [2010]
Theoretical CS, Physics, Math, Operations Research.
Applications: Combinatorial optimization problems on random graphs
(Max-Ind Set, random K-SAT, etc.)
Combinatorics.
Applications: graph limits.
Lovasz [2012], Hatami, Lovasz & Szegedy [2012], Elek & Lippner [2010],
Lyons & Nazarov [2011], Czoka & Lippner [2012]. I.I.D. factors.
Aldous [2012]. Invariant coding processes.
Local algorithms for combinatorial optimization problems.
Max-independent set problem
Local algorithms for combinatorial optimization problems.
K-SAT Problem
Ex:
II. Success stories
Correlation Decay Property
•
Low-Density-Parity-Check (LDPC) codes. Gallager [1960’s]
•
Karp-Sipser [1981] algorithm for Max-Independent-Set problem in
random graph
•
G, Goldberg & Weber [2010], algorithm for Max-Weight-Independent-Set
problem in arbitrary sparse graph
•
(Sequential) Local algorithms for counting/partition function computation
Weitz [2006], Bandyopadhyay & G [2006], Montanari & Shah [2007]
III. Random graphs. Structural results.
Max-Independent-Set problem
Theorem. [Frieze, Frieze & Luczak 1990s]. In graphs
III. Random graphs. Structural results.
Random K-SAT problem
Theorem. [Achlioptas & Peres 2003]. Satisfiability threshold ¼ 2K log 2
Algorithms?
Either local algorithms work or nothing else seems to works
Greedy algorithms for Max-Ind-Set problem
Set Unit Clause algorithm for K-SAT problem.
Algorithms?
Either local algorithms work or nothing else seems to works
Theorem. [Coja-Oghlan 2010-2011]. The Belief Propagation algorithm for
random K-SAT fails at
Extra log factor can be squeezed by a smarter algorithm
IV. Geometry of the solution space. Shattering. K-SAT
Insights from the Spin Glass theory
Mezard & Parisi [1980s]
Achlioptas & Ricci-Tersenghi [2004]
Mezard, Mora & Zecchina [2005]
Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova [2007]
IV. Geometry of the solution space. Shattering. Max-Ind-Set
Theorem. [Coja-Oghlan & Efthymiou 2010, G & Sudan 2012]
For every large enough d and every
there exist
such that no two independent sets of size
have intersection size between
and
V. Local algorithms as i.i.d. factors. Lovasz, Szegedy, Aldous.
Random n-node d-regular graph
V. Local algorithms as i.i.d. factors.
1. Fix r>0 and
2. Generate U1,…,Un uniformly at random and apply
i=1,…,n of the graph
3. Output
at every node
Local algorithms – i.i.d. factors
Conjecture. Hatami, Lovasz & Szegedy [2012] Max-Independent-Set
problem can be solved by means of local algorithms. Namely there
exists a sequence of functions
such that
Conjecture holds for Max-Matching:
Lyons & Nazarov [2011]
Abert, Csoka, Lippner & Terpai [2012]
Limits of local algorithms.
Theorem. [G & Sudan 2012] Hatami,Lovasz &Szegedy conjecture is not
valid. No local algorithm can produce an independent set larger than factor
of the optimal for large enough d.
• Proof idea: if an algorithm exists then one can construct two
independent sets with intersection in the non-existent region, violating
the shattering property.
• First direct link between shattering and algorithmic hardness
Proof sketch:
Suppose
exists such that
Construct two independent sets I and J using independent sources
U1,…,Un and V1,…,Vn
Then
Proof sketch (continued):
Continuously interpolate between U1,…,Un and V1,…,Vn : let
For each vertex , let
probability 1-p.
with probability p and
with
Consider independent set K obtained from
K=I when p=1 and K=J when p=0.
Fact:
all points in
- contradiction.
is continuous in p. Then we obtain intersection sizes for
Summary
I.
Local algorithms are relevant to many fields, beyond theory CS.
II.
Success of local algorithms is conditioned by establishing some form of the
correlation decay property.
III. For random graphs local algorithms often provide the best results.
IV.
Shattering property can be used as a proof technique for establishing
hardness results for local algorithms.
Ongoing work
I.
Non-existence of boolean 2-fanin circuits with depth
II.
Limits of Belief Propagation and Survey Propagation algorithms
based on the shattering phenomena.
Thank you