Challenges in Computational Complexity
Delve into the intriguing world of computational complexity with challenges ranging from linear transformations to matrix rigidity. Explore issues such as Gauss complexity, formula size, and communication complexity, presented through a series of thought-provoking problems and solutions.
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.
E N D
Presentation Transcript
Happy 60thBday Noga
Elementary problems encoding computational hardness or Some problems Noga never solved Avi Wigderson IAS, Princeton
Explicit object (graph, number, set,)n = - Explainable - Reasonable - Efficiently constructible - Not random - Not generic
Linear transformations Y1 . Y2 Yn + + M: Fn Fn + + + + y = Mx + + + c c + + + + X1 X2 . Xn For most M, size(M) n2 Challenge: Find M with size(M) O(n)
Gauss complexity F any field M an n n non-singular matrix over F. gc(M) = the smallest number of Gauss elimination steps to make M diagonal = min {s : M = E1E2 Es, Ei elementary} For most M, gc(M) n2 Challenge: Find explicit M with gc(M) O(n)
Matrix rigidity [Valiant] F any field M an n n matrix over F. M rigid if a all matrices in Hamming ball around it has high rank rig(M) = the smallest number of nonzeros in a matrix S such that rank(M-S) < n/10 For most M, rig(M) n2 Challenge: Find explicit M with rig(M) O(n)
Formula size f: {0,1}n {0,1} X1 X5 Xn -Xj Xj -X5 Fact: For most f, Fsize(f) exp(n) Thm Explicit f, Fsize(f) n3 Challenge: Find f with [Andreev, Hastad,Tal] Fsize(f) poly(n)
Composition[Karchmer-Raz-W] fg f: {0,1}n g: {0,1}k f g: {0,1}nk {0,1} f {0,1} {0,1} g g g Fact: For all f,g Fsize(f g) Fsize(f) Fsize(g) Challenge: Prove Fsize(f g) Fsize(f) Fsize(g) for some >0
Communication Complexity [Karchmer-W] 1 G 0 1 1 1 H 6 0 6 2 0 2 5 5 7 7 9 9 8 8 3 4 3 4 Alice non-Hamiltonian Hamiltonian Bob Alice and Bob communicate to solve: Task: Find (i,j) which is an edge in one of H or G Task*: Find (i,j) which is an edge in H but not G Fact: comm(Task) O(n) bits Challenge: Prove comm(Task) O(log n) bits Thm[KW]: comm(Task) log Fsize(Hamilton) Thm[Raz-W]: comm(Task*) (n) bits
Permanent & Determinant Detn(X) = Pern(X) = Sn sgn( ) i [n] Xi (i) Easy! i [n] Xi (i) Hard? Sn f + Arithmetic circuits + + Xi Xj Xi c
Determinantal complexity [Valiant] Affine mapL: Mn(F) dc(n): the smallest k for which there is a good map Mk(F) is good if Pern = Detk L a b c d a b -c d Thm[Polya]: dc(2) =2 Per2 = Det2 Thm[Valiant]: Thm[Mignon-Ressayre]: dc(n) > n2 Challenge: Prove dc(n) < exp(n) dc(n) poly(n) Thm[V]: Implies exponential lower bounds for Permanent
Polynomial identities [Heintz-Schnorr,Agrawal,Kabanets-Impagliazzo] 0 X1 Symbolic matrix M (0,1,X1 ,Xn) Is det(M) = 0 identically ? 0 X5 X1 Xn 1 X2 1 X1 n Xn Small Hitting Set (of small integer substitutions). Set k=n10 (say). H = {v1, v2, vk}, a set of vectors in [k]n det(M) 0 det(M(vi)) 0 for some i n Most H are small hitting sets Challenge: Find an explicit H Thm[A,KI]: Implies exponential lower bounds for Permanent
Elusive curves [Raz] Everything over C (works for other fields) Fact: The moment curve avoids every hyperplane! f(x) = (x,x2,x3, , xn) of degree n, avoids deg 1 maps: for every G: Cn-1 Cn of degree 1, Im(f) Im(G) / Challenge: Find an explicit curve of degree poly(n) which avoids all degree 2 maps. Thm[Raz]: Implies exponential lower bounds for Permanent
Sum-of-Squares [Hrubes-W- Yehudayoff] (X12+X22+ +Xk2)(Y12+Y22+ +Yk2) = B12+B22+ +Bn Bi=Bi(X,Y) Bilinear functions. n = n(k) k2 Do better? n=1 (X12)(Y12) = (X1Y1)2 n=2 (X12+X22)(Y12+Y22) = (X1Y2+X2Y1)2 + (X1Y1-X2Y2)2 n=4 (X12+ +X42)(Y12+ +Y42) = B12+B22+ +B42 Euler n=8 (X12+ +X82)(Y12+ +Y82) = B12+B22+ +B82 Hamilton Thm[Hurwitz] 1,2,4,8 are the only ones with n=k Thm[Radon] nZ(k) < k2/logk Thm[James] nR(k) > 2k Thm[HWY] nZ(k) > k6/5 Challenge: Prove nC(k) > k1+ Thm[HWY] exponential non-commutative circuit lower bound 2
[Razborov, Karchmer,W] The Fusion method Everything over GF(2) M1, M2, Mk, a list of n (works for other fields) n invertible matrices n-bit primes Finite ultrafilters Approximation method S a subset of [k]. MS = i S Mi Task: cover the universe {S: S odd, MS singular} composite P=(P1,P2,P3) is a 3-partition of [k]. P covers S if all three |S Pj| is odd. Fractional cover O(n) cov(n) = min size of covering family Challenge: Prove cov(n) O(n) Thm[R,KW] cov(n) is a circuit lower bound for Determinant Primality
Why do Lower bounds manifest themselves in so many ways? Computation is everywhere!
Happy 60thBday Noga
