Understanding Circuit Minimization in Complexity Theory
Dive into the new complexity landscape surrounding circuit minimization, exploring topics such as the Minimum Circuit Size Problem, Meta-Complexity, Theory of Learning, and basic facts about MCSP. Discover the connections to learning theory and the implications for computational complexity.
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
The New Complexity Landscape around Circuit Minimization Eric Allender Rutgers University LATA 2020/2021 Keynote Milan, September 20, 2021 Eric Allender: The New Complexity Landscape around Circuit Minimization <1>
A Complex Landscape Eric Allender: The New Complexity Landscape around Circuit Minimization <2>
The Minimum Circuit Size Problem Much of the attention in this area focuses on MCSP (the Minimum Circuit Size Problem): MCSP = {(f,i) : Size(f) i} Size(f) is the number of gates (or wires?) in the smallest circuit computing the function f. f is a bit string of length 2n (the truth table of a Boolean function). Different versions of MCSP may have different complexity. (???) Eric Allender: The New Complexity Landscape around Circuit Minimization <3>
Meta-Complexity Complexity Theory asks: What is the complexity of f? That is: Is it hard to compute f? Meta-Complexity asks: Is it hard to determine if it is hard to compute f? That is: Is Complexity Theory Hard? Eric Allender: The New Complexity Landscape around Circuit Minimization <4>
Meta-Complexity Recall: MCSP = {(f,i) : Size(f) i} Thus an instance (f,i) asks the complexity question Does f have circuit complexity at most i? The Meta-Complexity question is: What is the complexity of MCSP? Eric Allender: The New Complexity Landscape around Circuit Minimization <5>
Theory of Learning MCSP is also closely connected to learning theory. Canonical learning problem: given a list of yes instances and no instances, find an efficient circuit that explains this data, and will attempt to classify new instances. This is MCSP for partially-specified functions (Partial-MCSP). Eric Allender: The New Complexity Landscape around Circuit Minimization <6>
Some Basic MCSP Facts MCSP is in NP. [RR,KC]: If MCSP is in P/poly, then there are no cryptographically-secure one-way functions. [AD]: MCSP is hard for SZK under BPP-Turing reductions. [MW]: If MCSP is NP-hard under p reductions, then EXP ZPP. [MW]: MCSP is not hard for PARITY under n1/3-time local reductions. ? Eric Allender: The New Complexity Landscape around Circuit Minimization <7>
Local Reductions Output Given i, can compute ith bit of output in time t(n) Input Eric Allender: The New Complexity Landscape around Circuit Minimization <8>
Some Basic MCSP Facts MCSP is in NP. [RR,KC]: If MCSP is in P/poly, then there are no cryptographically-secure one-way functions. [AD]: MCSP is hard for SZK under BPP-Turing reductions. [MW]: If MCSP is NP-hard (or even RP-hard [Fu]) under p ?reductions, then EXP ZPP. [MW]: MCSP is not hard for PARITY under n1/3-time local reductions. Eric Allender: The New Complexity Landscape around Circuit Minimization <9>
Complexity Classes EXP PSPACE coNP NP P/poly BPP coRP RP ZPP P Eric Allender: The New Complexity Landscape around Circuit Minimization <10>
Some Basic MCSP Facts MCSP is in NP. [RR,KC]: If MCSP is in P/poly, then there are no cryptographically-secure one-way functions. [AD]: MCSP is hard for SZK under BPP-Turing reductions. [MW]: If MCSP is NP-hard (or even RP-hard [Fu]) under p ?reductions, then EXP ZPP. [MW]: MCSP is not hard for PARITY under n1/3-time local reductions. Eric Allender: The New Complexity Landscape around Circuit Minimization <11>
Statistical Zero Knowledge SZK is nearly inside NP coNP (and is probably completely inside NP coNP). coNP NP MCSP SZK Eric Allender: The New Complexity Landscape around Circuit Minimization <12>
Some Basic MCSP Facts MCSP is in NP. [RR,KC]: If MCSP is in P/poly, then there are no cryptographically-secure one-way functions. [AD]: MCSP is hard for SZK under BPP-Turing reductions. [MW]: If MCSP is NP-hard (or even RP-hard [Fu]) under p ?reductions, then EXP ZPP. [MW]: MCSP is not hard for PARITY under n1/3-time local reductions. Eric Allender: The New Complexity Landscape around Circuit Minimization <13>
Pseudorandom Generators Gf seed PseudoRandom bits b1,b2, [HILL]: For any poly-time f, we can build a generator Gf. If T is a test that accepts a smaller fraction of Gf pseudorandom strings than uniformly random strings, then we can use T to invert f whp. Eric Allender: The New Complexity Landscape around Circuit Minimization <14>
Pseudorandom Generators Gf seed PseudoRandom bits b1,b2, The output of Gfhas small time-bounded K-complexity. Eric Allender: The New Complexity Landscape around Circuit Minimization <15>
Pseudorandom Generators Gf seed PseudoRandom bits b1,b2, The output of Gfhas small time-bounded K-complexity. KT(x) Circuit.size(x). Eric Allender: The New Complexity Landscape around Circuit Minimization <16>
Pseudorandom Generators Gf seed PseudoRandom bits b1,b2, The output of Gfhas small time-bounded K-complexity. KT(x) Circuit.size(x). Most x require very large circuits. Eric Allender: The New Complexity Landscape around Circuit Minimization <17>
Pseudorandom Generators seed PseudoRandom bits b1,b2, The output of Gfhas small time-bounded K-complexity. KT(x) Circuit.size(x). Most x require very large circuits. MCSP gives us a great test T to distinguish random and pseudorandom strings. Eric Allender: The New Complexity Landscape around Circuit Minimization <18>
Kolmogorov Complexity K(x) = min {|d| : U(d)=x}. Information is best understood via computation; this gives us a definition of randomness. Eric Allender: The New Complexity Landscape around Circuit Minimization <19>
Kolmogorov Complexity K(x) = min {|d| : U(d)=x}. Here, U is some Universal TM. KU1(x) KU2(x) [ Invariance ] Eric Allender: The New Complexity Landscape around Circuit Minimization <20>
Kolmogorov Complexity K(x) = min {|d| : U(d)=x}. Great for many purposes but not computable. Eric Allender: The New Complexity Landscape around Circuit Minimization <21>
Time-bounded Kolmogorov Complexity A first attempt: Kt(n)(x) = min {|d| : U(d)=x in time t(|x|)}. Problem: No invariance! There are workarounds, but they re messy. Still, we ll need to refer to this notion, especially when t(n) = nkfor some k, or when t(n) = 2n for some >0. Let s call these Kpolyand Kexp, respectively. No clear connection to circuit complexity Eric Allender: The New Complexity Landscape around Circuit Minimization <22>
Time-bounded Kolmogorov Complexity Kt(x) = min {|d| + log t : U(d)=x in time t}. Great for many purposes and invariance holds but captures an odd type of circuit size. Eric Allender: The New Complexity Landscape around Circuit Minimization <23>
Circuit Complexity Let D be a circuit of AND and OR gates (with negations at the inputs). Size(D) = # of wires in D. Size(f) = min{Size(D) : D computes f} We may allow oracle gates for a set A, along with AND and OR gates. SizeA(f) = min{Size(D) : DA computes f} Eric Allender: The New Complexity Landscape around Circuit Minimization <24>
What is an Oracle Gate? An oracle gate for oracle B is a piece of hardware with k wires coming in (for some k). If those wires take on the value x, then the gate outputs 1 if x is in B, and 0 otherwise. B Eric Allender: The New Complexity Landscape around Circuit Minimization <25>
Time-Bounded Kolmogorov Complexity Levin s definition: Kt(x) = min{|d|+log t : U(d) = x in time t}. but captures an odd type of circuit size. Let A be complete for E = Dtime(2O(n)). Then Kt(x) SizeA(x). Computing Kt(x) is complete for EXP under P/poly reductions and NP-Turing reductions. Kt(x) is computable in ZPP iff ZPP=EXP but is it hard for EXP under ZPP-reductions? Eric Allender: The New Complexity Landscape around Circuit Minimization <26>
Time-Bounded Kolmogorov Complexity Levin s definition: Kt(x) = min{|d|+log t : U(d) = x in time t}. but captures an odd type of circuit size. Let A be complete for E = Dtime(2O(n)). Then Kt(x) SizeA(x). Computing Kt(x) is complete for EXP under P/poly reductions and NP-Turing reductions. [Hirahara]: Computing Kexpis complete for EXP under ZPP-Turing reductions. Eric Allender: The New Complexity Landscape around Circuit Minimization <27>
Time-Bounded Kolmogorov Complexity Levin s definition: Kt(x) = min{|d|+log t : U(d) = x in time t}. but captures an odd type of circuit size. Let A be complete for E = Dtime(2O(n)). Then Kt(x) SizeA(x). Neither Kt(x) nor Kexpis complete for EXP under p ?reductions. Eric Allender: The New Complexity Landscape around Circuit Minimization <28>
Time-Bounded Kolmogorov Complexity Levin s definition: Kt(x) = min{|d|+log t : U(d) = x in time t}. but captures an odd type of circuit size. Let A be complete for E = Dtime(2O(n)). Then Kt(x) SizeA(x). Open question: Can Kt(x) be computed in polynomial time? [Hirahara]: Kexp(x) can not be! Eric Allender: The New Complexity Landscape around Circuit Minimization <29>
Time-Bounded Kolmogorov Complexity Levin s definition: Kt(x) = min{|d|+log t : U(d) = x in time t}. Why log t? This gives an optimal search order for NP search problems. Adding t instead of log t would give every string complexity |x|. So let s look at how to make the run-time be much smaller. Eric Allender: The New Complexity Landscape around Circuit Minimization <30>
Revised Kolmogorov Complexity K(x) = min{|d| : for all i |x| + 1, U(d,i,b) = 1 iff b is the i-th bit of x} (where bit # i+1 of x is *). This is identical to the original definition. Kt(x) = min{|d|+log t : for all i |x| + 1, U(d,i,b) = 1 iff b is the i-th bit of x, in time t}. The new and old definitions are within O(log |x|) of each other. Define KT(x) = min{|d|+t : for all i |x| + 1, U(d,i,b) = 1 iff b is the i-th bit of x, in time t}. Eric Allender: The New Complexity Landscape around Circuit Minimization <31>
Kolmogorov Complexity is Circuit Complexity KT(x) Size(x). K(x) KTH SizeH(x). Kt(x) KTE SizeE(x). Other measures of complexity can be captured in this way, too: Branching Program Size KB(x) = min{|d|+2s: for all I |x| + 1, U(d,i,b) = 1 iff b is the i-th bit of x, in space s}. Eric Allender: The New Complexity Landscape around Circuit Minimization <32>
Kolmogorov Complexity is Circuit Complexity KT(x) Size(x). K(x) KTH SizeH(x). Kt(x) KTE SizeE(x). Other measures of complexity can be captured in this way, too: Formula Size KF(x) = min{|d|+2t: for all I |x| + 1, U(d,i,b) = 1 iff b is the i-th bit of x, in time t}, for an alternating Turing machine U}. Eric Allender: The New Complexity Landscape around Circuit Minimization <33>
Moral: Information = Circuit Complexity The amount of accessible information in an object can be approximated by the circuit complexity required to compute the function represented by the object (on the appropriate class of circuits). Eric Allender: The New Complexity Landscape around Circuit Minimization <34>
Another connection Another measure of information comes from the entropy of a probability distribution. In complexity theory an important question (giving rise to complete problems for SZK) deals with computing the entropy of a distribution, represented by a circuit C with m inputs and n outputs. Useful fact [AGvMMM]: take t samples of C(r) for random r and concatenate them to obtain y. Then H(C) KT(y)/t. Eric Allender: The New Complexity Landscape around Circuit Minimization <35>
Meta-Complexity Thus, in order to understand MCSP, we will study: MKTP = {(x,i) : KT(x) i} since KT Circuit Size. Note: There are many different versions of MCSP, depending on the types of gates allowed, different measures of size , etc. It s possible that different versions have very different complexity. Eric Allender: The New Complexity Landscape around Circuit Minimization <36>
Meta-Complexity Thus, in order to understand MCSP, we will study: MKTP = {(x,i) : KT(x) i} since KT Circuit Size. MKTP is, in some sense, the most convenient of these versions. All theorems known for MCSP hold also for MKTP; some results known for MKTP are not (yet) known to hold for MCSP. Eric Allender: The New Complexity Landscape around Circuit Minimization <37>
NISZK Non-Interactive Statistical Zero Knowledge Eric Allender: The New Complexity Landscape around Circuit Minimization <38>
Complexity of MCSP/MKTP MCSP is hard for SZK under BPP-Turing reductions. [A,Das] MKTP is also hard for SZK under nonadaptive BPP-Turing reductions, and is hard for coNISZK under P/poly m-reductions. [AGHR] but what about p ?reductions? Eric Allender: The New Complexity Landscape around Circuit Minimization <39>
Complexity of MCSP/MKTP [Murray, Williams]: MCSP is not NP-complete under p ?reductions, unless ZPP EXP. [Fu]: MCSP is not even hard for ZPP under p reductions, unless ZPP EXP. Not evidence against NP-completeness but evidence that completeness will be difficult to prove. [MW]: MCSP is not even hard for PARITY under ?-Time Local reductions. ? Eric Allender: The New Complexity Landscape around Circuit Minimization <40>
Complexity of MKtP [Hirahara]: MKtP is not NP-hard under p reductions, unless ZPP EXP. [Fu]: MKtP is not even hard for ZPP under ? (nonadaptive) reductions, unless ZPP EXP. Not evidence against NP-hardness but evidence that hardness will be difficult to prove. BUT . be careful . [AHK]: MKtP is not NP-hard under p reductions, unless EXP = NEXP!!!!! ? ?? ? Eric Allender: The New Complexity Landscape around Circuit Minimization <41>
NP-completeness for variants Here are some variants of MCSP that are NP- complete under p ?reductions DNF formulas [Masek, 1979] DNF of MODs [HOS, 2018] Deterministic Communication Complexity of partial functions [ILO, 2020] k-round Deterministic Communication Complexity [HIL, 2021] Nondeterministic Communication Complexity [Orlin, 1977] Eric Allender: The New Complexity Landscape around Circuit Minimization <42>
NP-completeness for variants And here are some variants complete under randomized poly-time reductions: Conditional KT complexity McKTP = {(x,y,i) : KT(x|y) i} [ACMTV] [Ilango 2020] (Not hard for ZPP under p Aside: [Hirahara20] showed that McKpolyPSAT is hard for PNPunder deterministic nonadaptive reductions. (Not true for MCSPSATif ZPP = EXP.) ?if ZPP = EXP.) Eric Allender: The New Complexity Landscape around Circuit Minimization <43>
NP-completeness for variants And here are some variants complete under randomized poly-time reductions: Conditional KT complexity McKTP = {(x,y,i) : KT(x|y) i} [ACMTV] [Ilango 2020] (Not hard for ZPP under p Circuit Size for multi-output functions [ILO] and under randomized quasipolynomial-time reductions: Depth d AC0formula size [Ilango 2020] ?if ZPP = EXP.) Eric Allender: The New Complexity Landscape around Circuit Minimization <44>
Unconditional Lower Bounds MCSP is not in AC0[p] for any prime p [GIIKKT] De Morgan Formula Size n3- [CKLM] Branching Program Size n2- [CKLM] AC0depth d size 2n1/(d+2.2) [CKLM] MKTP is not in THRESHOLDoMAJORITY size 2no(1) [AGHR] Nondeterministic Branching Program Size n1.5/log n [CHMY] Eric Allender: The New Complexity Landscape around Circuit Minimization <45>
Lower Bounds and Magnification Define MCSP[s] = {f : (f,s) is in MCSP} [CHMY]: MCSP[N ] is not in probabilistic 1- tape TM time N1.99. [MMW]: If MCSP[N ] is not in 1-tape TM time N1.01, then P NP. Note: < General theme of Magnification: modest- sounding lower bounds can have huge consequences. Eric Allender: The New Complexity Landscape around Circuit Minimization <46>
Lower Bounds and Magnification Another example: Recall: MCSP is not in De Morgan Formula Size n3- [CKLM] This holds also for MKTP and MKtP. If MKtP[N ] is not in De Morgan Formula Size n3.001, then EXP is not in NC1[OPS]. but perhaps you re thinking: We don t have ANY formula size lower bounds that big. Then consider this Eric Allender: The New Complexity Landscape around Circuit Minimization <47>
Lower Bounds and Magnification Yet another example: If MKtP[N ] is not in De Morgan Formula of PARITY Size n1.1, then EXP is not in NC1 [OPS]. and we do know problems in P that require size n1.99in this model [Tal]. For more on magnification, see [CHOPRS]. Eric Allender: The New Complexity Landscape around Circuit Minimization <48>
Meta-Complexity and Crypto Much of the current interest in MCSP traces back to the work of Razborov and Rudich on Natural Proofs. The set of truth tables requiring large circuits is an archtypical combinatorial property in a Natural Proof. [Kabanets, Cai, 2000]: If MCSP is easy, then there are no cryptographically-secure one-way functions. The connection between one-way functions and meta-complexity has grown much stronger recently. Eric Allender: The New Complexity Landscape around Circuit Minimization <49>
Meta-Complexity and Crypto One-way functions are essential for cryptography. But good candidate one-way functions can be hard to justify. Levin gave a construction of a function that is one-way if any one-way function exists, but it s not very natural and has little utility in practice. [Liu, Pass] Cryptographically-secure one-way functions exist iff MKpolyP is Hard on Average. Eric Allender: The New Complexity Landscape around Circuit Minimization <50>
