Probabilistic Method: New Frontiers and Old Challenges

This content delves into the probabilistic method, highlighting its significance in tackling new frontiers and overcoming old challenges. Shachar Lovett, from UCSD, shares insights at the ELC Tokyo Complexity Workshop in March 2013, shedding light on advancements and persistent obstacles in this area of study. Exploring the intersection of theory and applications, this session is a valuable resource for researchers and enthusiasts looking to understand and navigate the intricate realm of probabilistic reasoning.

• Probabilistic Method
• Shachar Lovett
• UCSD
• Complexity Workshop
• ELC Tokyo

karl_eda Follow

Uploaded on Mar 05, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. The probabilistic method: New frontiers and old challenges Shachar Lovett (UCSD) ELC Tokyo Complexity Workshop, March 2013

2. 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,

3. 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 !

4. Example: bad movies How to find a bad movie pick one at random! Photo courtesy of elijahconsulting.com

5. 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

6. Example: good codes CODEWORD MINIMAL DISTANCE AROUND CODEWORD

7. 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

8. 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,

9. 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,

10. 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

11. 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

12. 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

13. 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

14. Lovsz 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

15. Lovsz 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?

16. Lovsz local lemma d-regular graph, color vertices {-1,+1}, minimize absolute sum of neighbors

17. Lovsz local lemma d-regular graph, color vertices {-1,+1}, minimize absolute sum of neighbors - + + - - - + + + + - +

18. Lovsz local lemma d-regular graph, color vertices {-1,+1}, minimize absolute sum of neighbors - abs sum: 3 + + - - - + + + + - +

19. Lovsz 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) ( log( )) O d d Lov sz local lemma: can get That is, there are rare colorings which are much better than typical colorings Beck-Fiala conjecture (special case): can get ( ) O d

20. Lovsz 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

21. Lovsz 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!!!

22. 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

23. 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

24. 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: ??? ? log ? 12 1 2? [Alexander 90, Matou ek 95]

25. 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 True answer: O n ( log( )) O n n 1/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)

26. 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 Beats the for random colorings For m=n gets Previously mentioned results use the same proof technique + domain specific knowledge ( log( log( )) 6 n / )) O ( n m n O n m

27. 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

28. Some applications of algorithmic discrepancy theory Phase transition for random integer programs [Chandrasekaran-Vempala 12] Improved approximation algorithm for bin- packing [Rothvoss 13] Codes with bounded peak-to-mean envelope [Work in progress with Kotzer, Litsyn]

29. 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: ? Best constructive bound: ? Special case of yet another conjecture (Komlos conjecture) ? ?log?[Banaszczyk 97] ? log? Constructive versions of the domain specific applications of Spencer s theorem

30. 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

31. Regular structures Combinatorial structures with regular symmetric structure Examples: Regular graphs Designs K-wise permutations

32. 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?

33. 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

34. 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

35. 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

36. 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

37. 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]

38. Common scenarios Very regular objects Explicit constructions known in few cases, if any When constructions are unknown, so is existence

39. 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 d- regular graphs (and forget for a minute that we know how to construct them explicitly)

40. 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

41. Probabilistically constructing d-regular graphs G random graph on n vertices, each edge is independently chosen with probability ? = ? ? 1 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

42. 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)

43. 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

44. 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

45. 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

46. 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?

47. 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)

48. 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

49. 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

50. 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

Load More ...