Complexity in Computational Theory
Happy 60
th
B’day
Mike
Lower bounds, anyone?
Avi Wigderson
Institute for Advanced Study
Lower bounds
&
Randomness
&
Expanders
P = NP
?
Big
DATA
NP = coNP
?
Mike’s dictionary
:
Comput. Complexity
Set Theory
Polynomial ~ Countable
Exponential ~ Uncountable
NP
coNP
Polysize Nondet DNF Polysize Nondet CNF
Countable Nondet DNF Countable Nondet CNF
Analytic coAnalytic
[Sipser]
New, “more combinatorial” proof
Topological
approach
P = NP
?
PH = PSPACE
?
[BGS]
A
P
A
NP
A
(diagonalization is useless)
?
A
PH
A
PSPACE
A
?
Mike’s dictionary
Oracle machines
Circuit comp.
Set theory
PH
A
~ AC
0
~ Finite Borel hierarchy
PSPACE
A
~ NC
1
~ Borel sets
[Sipser]
New, “more combinatorial” proof
[Furst-Saxe-Sipser,Ajtai]
Parity
AC
0
[Yao, Hastad]
A
PH
A
PSPACE
A
Switching Lemma,
Restrictions
Random
NL = L
?
Mike’s dictionary
Comp classes
Finite automata
NL
~ poly
size
2NFA
L
~ poly
size
2DFA
[Sipser]
n
language S
n
such that
-
S
n
is accepted by an O(
n
)-state 2NFA
-
S
n
requires 2
n
-state (
sweeping
) 2DFA
REGULAR = 2DFA = 2NFA = 2PFA*
[Open]
2
AM
FA* = REGULAR
?
[CHPW]
True if
2
AM
FA* = co2
AM
FA*
*
Polytime
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
)
or
BPP
=
P
if
Explicit extractors exist
X
Hardness vs.
Randomness
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]
PublicCoin
IP
= PrivateCoins
IP
Randomness & Lower bounds
Probabilistic method (AC0)
Natural proofs
NC
1
vs. P
- Can sequential computation be parallelized?
- Are formulas weaker than circuits?
Composition
g
:{0,1}m
{0,1}f
:{0,1}n
{0,1}g
o
f
:{0,1}mn
{0,1}D(
g
o
f
) ≤ D(
g
)+D(
f
), L(
g
o
f
) ≤ L(
g
) L(
f
)
[Karchmer-Raz-Wigderson Conj]
This is tight!
The KRW conjecture
[KRW
conj]
: D(
g
o
f
) ≈ D(
g
)+D(
f
)
[KRW]
: Conjecture implies
P
≠
NC
1
.
[KRW]
: Conjecture holds for monotone circuits
[Cor]
:
m
P
≠ m
NC
1
.
[Grigni-Sipser]
:
m
L
≠ m
NC
1
.
Natural proof
Barrier doesn’t
Seem to apply
KRW program
Universal Relations:
g
≤
U
m
,
f
≤
U
n
,
g
o
f
<
U
m
o
U
n
[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(U
m
o
f
) ≈ D(U
m
) + D(
f
)
Happy 60
th
b’day Mike!!!
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!!!
