Exploring Complexity in Computational Theory
Dive into a world of computational complexity and theory with a focus on topics such as NP, P, PH, PSPACE, NL, L, random vs. deterministic algorithms, and the interplay of time and space complexity. Discover insights on lower bounds, randomness, expanders, noise removal, and the intriguing question of P vs. NP. Delve into conceptually rich content showcasing the vast landscape of theoretical computer science.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Happy 60thBday Mike
Lower bounds, anyone? Avi Wigderson Institute for Advanced Study
Lower bounds & Randomness & Expanders
Removing noise Neuro Internet Genetic algor Language Sampling Visual Prediction Regularities HMM Generative grammar Statistical mechanics Translation Annealing Low dim surface What is going on? Bayesian network Clustering Neural network Correlations Big DATA SVD Seismic Essential parameters Dimension reduction Stock Market Decision tree Occam s razor LHC Boosting Genomic Astronomical Gradient descent Irregularities Weather
NP = coNP ? Mike s dictionary: Comput. Complexity Polynomial ~ Countable Exponential ~ Uncountable Set Theory NP coNP Polysize Nondet DNF Polysize Nondet CNF Countable Nondet DNF Countable Nondet CNF Analytic coAnalytic Topological approach [Sipser] New, more combinatorial proof
P = NP ? PH = PSPACE ? [BGS] A PA NPA (diagonalization is useless) ? A PHA PSPACEA ? Mike s dictionary Oracle machines PHA ~ AC0 ~ Finite Borel hierarchy PSPACEA ~ NC1 ~ Borel sets Circuit comp. Set theory [Sipser] New, more combinatorial proof [Furst-Saxe-Sipser,Ajtai] Parity AC0 [Yao, Hastad] A PHA PSPACEA Switching Lemma, Restrictions Random
NL = L ? Mike s dictionary Comp classes NL ~ polysize 2NFA L ~ polysize 2DFA Finite automata [Sipser] n language Snsuch that - Snis accepted by an O(n)-state 2NFA - Snrequires 2n-state (sweeping) 2DFA * Polytime REGULAR = 2DFA = 2NFA = 2PFA* [Open] 2AMFA* = REGULAR ? [CHPW] True if 2AMFA* = co2AMFA*
Time vs. Space [HPV] Time(t) Space(t/log t) [Open] Time(t) Space(t.99) ? Randomness vs. Determinism [Open] BPP = P ? [Sipser] either Time(t) Space(t.99) orBPP =P Hardness vs. Randomness if Explicit extractors exist X
Utilizing Expanders [Sipser] Expanders T(t) S(t.99) or BPP = P [Karp-Pippenger-Sipser] Deterministic amplification [Sipser-Spielman] Expander codes ( [Gallager, Tanner] ) [Spielman] linear time encoding and decoding good codes [Sipser?] Affine expander? [Klawe] Impossibility!
Hashing in Comput. Complexity [Sipser] BPP PH [Gacs, Lautemann] [Goldwasser-Sipser] PublicCoinIP = PrivateCoinsIP
Randomness & Lower bounds Probabilistic method (AC0) Natural proofs
NC1 vs. P - Can sequential computation be parallelized? - Are formulas weaker than circuits? gof g Composition g:{0,1}m f:{0,1}n gof:{0,1}mn {0,1} {0,1} {0,1} f f D(gof) D(g)+D(f), L(gof) L(g) L(f) [Karchmer-Raz-Wigderson Conj] This is tight!
The KRW conjecture [KRW conj]: D(gof) D(g)+D(f) Natural proof Barrier doesn t Seem to apply [KRW]: Conjecture implies P NC1. [KRW]: Conjecture holds for monotone circuits [Cor]: mP mNC1. [Grigni-Sipser]: mL mNC1.
KRW program Universal Relations: g Um, f Un, gof < UmoUn [EIRS, HW]: D(Um o Un) D(Um) + D(Un) [GMWW 13]: g D(g o Un) D(g) + D(Un) [Open]: g,f D(g o f) D(g) + D(f) [Open]: f D(Um o f) D(Um) + D(f)
Happy 60th b day Mike!!!
