Nycac 2015: Graph Automorphism and Circuit Size

NYCAC 2015: Graph Automorphism and Circuit Size

• NYCAC 2015: Graph Automorphism and Circuit Size

• NYCAC 2016: New Insights on the (Non)hardness of Circuit Minimization and Related Problems

• NYCAC 2017: Minimum Circuit Size, Graph Isomorphism, and Related Problems

• All about MCSP and GA or GI.
• … and about the “related problem”: MKTP

The Minimum Circuit Size Problem (MCSP) = {(f,i) : f is the truth-table of a function that has a circuit of size ≤ i}.

• The Minimum Circuit Size Problem (MCSP) = {(f,i) : f is the truth-table of a function that has a circuit of size ≤ i}.

• In NP, but not known (or widely believed) to be NP-complete. [Kabanets, Cai], [Murray, Williams], [A, Holden,Kabanets], [Carmosino, Impagliazzo,Kabanets,Kolokova], [Hirahara, Santhanam], [Hirahara,Watanabe], [Hitchcock, Pavan], [Impagliazzo,Kabanets,Volkovich]…

• Lots of reasons to believe it’s not in P.

Factoring is in ZPPMCSP.

• Factoring is in ZPPMCSP.

• Graph Isomorphism is in RPMCSP.

• Every promise problem in SZK is in (Promise) BPPMCSP.

• A motivating question: Is Graph Isomorphism in ZPPMCSP?

Factoring is in ZPPMCSP.

• Factoring is in ZPPMCSP.

• Graph Isomorphism is in RPMCSP.

• Every promise problem in SZK is in (Promise) BPPMCSP.

• An obstacle: EACH of these reductions follows the same route….

The well-trodden path:

• The well-trodden path:

• MCSP is a wonderful test to distinguish random from pseudorandom distributions.

• Thus, via [HILL], MCSP is an oracle that allows a probabilistic algorithm to invert poly-time functions with high probability.

• Note that this approach can’t show a result like “A is in ZPPMCSP” unless we already know that A is in NP∩coNP.

MCSP is more like a family of problems, than a single problem.

• MCSP is more like a family of problems, than a single problem.

• For instance “size” could mean “# of wires” or “# of gates”, or “# of bits to describe the circuit”, etc.

• None of these is known to be reducible to any other – but all can stand in for “MCSP”.

• One more such variant: MKTP = {(x,i) : KT(x) ≤ i}

Graph Automorphism is in ZPPMKTP.

• Graph Automorphism is in ZPPMKTP.

• As observed on an earlier slide, this involves a different type of reduction than all earlier reductions to MKTP or MCSP (since Graph Automorphism is not known to be in NP∩coNP).

• We are unable to extend this, to show Graph Automorphism is in ZPPMCSP.

• This is a new phenomenon; all other reductions to MKTP carried over to MCSP.

Graph ISOmorphism is in ZPPMKTP!

• Graph ISOmorphism is in ZPPMKTP!

• As observed on an earlier slide, this involves a different type of reduction than all earlier reductions to MKTP or MCSP (since Graph Automorphism is not known to be in NP∩coNP).

• We are unable to extend this, to show Graph Automorphism is in ZPPMCSP.

• This is a new phenomenon; all other reductions to MKTP carried over to MCSP.

A big chunk of SZK is in ZPPMKTP!

• A big chunk of SZK is in ZPPMKTP!

• As observed on an earlier slide, this involves a different type of reduction than all earlier reductions to MKTP or MCSP (since Graph Automorphism is not known to be in NP∩coNP).

• We are unable to extend this, to show Graph Automorphism is in ZPPMCSP.

• This is a new phenomenon; all other reductions to MKTP carried over to MCSP.

MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• Levin delayed publishing his results on SAT and NP, because he wanted to prove a similar result about MCSP.

MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• Why was Levin so interested in MCSP?

• In the USSR in the 70’s (and before) there was great interest in problems requiring “perebor”, or “brute-force search”. For various reasons, MCSP was a focal point of this interest.

MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• Why was Levin so interested in MCSP?

• Yablonski [1959] proved a result that – to him and his students – meant “MCSP requires perebor”. (This would imply P < NP.) By the late 1960’s Yablonski “attained influential positions [dealing with] coordination and control of math…a time of rapid degradation of the moral climate within the Soviet math community” [Trakhtenbrot].

MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• MCSP = {(x,i) : x is the truth table of a function with a circuit of size at most i}.

• MCSP is in NP. (Guess a circuit of size ≤ |x|, and verify that it gives the correct answer for each y of length log |x|.)

• If MCSP is NP-complete, then EXP is not equal to ZPP [Murray & Williams, 2015].

• A prominent candidate for “NP-intermediate” status.

If MCSP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MCSP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MCSP is NP-complete under uniform AC0 reductions, then NP is not in P/poly [MW15].

If MKTP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MKTP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MKTP is NP-complete under uniform AC0 reductions, then NP is not in P/poly [MW15].

• If MKTP is NOT NP-complete under nonuniform AC0 reductions, then NP is not equal to DET. [A,Hirahara]

• Is there an obstacle that prevents a proof today, that MKTP is NP-complete under non-uniform reductions?

If MKTP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MKTP is NP-complete under poly-time reductions, then EXP is not equal to ZPP [MW15].

• If MKTP is NP-complete under uniform AC0 reductions, then NP is not in P/poly [MW15].

• If MKTP is NOT NP-complete under nonuniform AC0 reductions, then NP is not equal to DET. [A,Hirahara]

• Is there an obstacle that prevents a proof today, or that MKTP is NOT NP-complete under uniform reductions?

RP: Like NP, but with many witnesses.

• RP: Like NP, but with many witnesses.

GI = {(G,H) : the vertices of G can be permuted, to yield H}

• GI = {(G,H) : the vertices of G can be permuted, to yield H}

The Graph Isomorphism problem was one of the first few problems known to have a Zero Knowledge Interactive Proof.

• The Graph Isomorphism problem was one of the first few problems known to have a Zero Knowledge Interactive Proof.

The Graph Isomorphism problem was one of the first few problems known to have a Zero Knowledge Interactive Proof.

• The Graph Isomorphism problem was one of the first few problems known to have a Zero Knowledge Interactive Proof.

SZK is contained in NP/poly ∩ coNP/poly.

• SZK is contained in NP/poly ∩ coNP/poly.

• There are complete problems for SZK.

• …but in order to introduce these complete problems, we need to talk about “promise problems”.

RIGID GI:

• RIGID GI:

• YES: {(G,H) :G and H are rigid, and G≡H}
• NO: {(G,H) :G and H are rigid, and G≡H}

• Entropy Approximation

• YES: {(C,θ) : the entropy of the distribution generated by C is > θ+1}
• NO: {(C,θ) : the entropy of the distribution generated by C is < θ-1}

Entropy Approximation is complete for SZK under poly-time Turing reductions [Goldreich, Sahai, Vadhan]

• Entropy Approximation is complete for SZK under poly-time Turing reductions [Goldreich, Sahai, Vadhan]

Outline for the rest of the talk.

• Outline for the rest of the talk.

• 1. Give a reduction from RIGID Graph Isomorphism to MKTP.

• 2. Discuss why we were stuck at this point for a while.

• 3. Sketch how MKTP allows us to estimate the value (n!/|Aut(G)|), via “entropy estimation”.

• 4. Discuss how MKTP allows us to estimate the entropy in (almost) flat distributions.

On input (G0,G1)

• On input (G0,G1)

• Randomly pick a bit string w=w1w2…wt.
• Pick random permutations π1…πt.
• Let z= π1(Gw1)π2(Gw2)…πt(Gwt)

• If G0 and G1 are not isomorphic, then z allows us to reconstruct w and π1…πt, so that z has (non-time-bounded) K-complexity around t+ts (where s = log n!), whp. Hence KT(z) > t+ts.

• Otherwise, KT(z) is around n2+ts.

The critical line in the previous slide is: “s = log n!”, because a random permutation π has KT complexity about s, with high probability.

• The critical line in the previous slide is: “s = log n!”, because a random permutation π has KT complexity about s, with high probability.

• But if the graphs are NOT rigid, then the entropy in π(G) is (n! / |Aut(G)|).

• …and computing |Aut(G)| is as hard as Graph Automorphism!

• Solution: Use the MKTP oracle!

We already knew that GI BPP-reduces to MKTP.

• We already knew that GI BPP-reduces to MKTP.

• With an oracle for GI, we can produce a list of generators for Aut(G) w.h.p. (Pick a new permutation, and see if it’s in Aut(G) and is not already in the group generated by the previous permutations.) We can compute the size of the group generated by our list of permutations.

• Thus this can be done with MKTP as an oracle. (Lots of details, to make this a ZPP reduction.)

Let D be a distribution.

• Let D be a distribution.

• Max-Entropy = min {k : for all x D(x) > 1/2k}

• Entropy = E[log(1/D(x))]

• Min-Entropy = max {k : for all x D(x) < 1/2k}

Let D be a distribution represented by circuit C. (That is, D(x) = Proby[C(y)=x].)

• Let D be a distribution represented by circuit C. (That is, D(x) = Proby[C(y)=x].)

• Let Δ be the difference between the max-entropy and the min-entropy of D.

• Let z be the concatenation of t random samples from D.

• Then KT(z)/t is a probably-approximately-correct underestimator for the entropy of D, with deviation Δ.

• Proof: Establish a connection between Hashing and KT complexity.

Are there any interesting problems reducible to “Entropy Estimation for Flat Distributions”?

• Are there any interesting problems reducible to “Entropy Estimation for Flat Distributions”?

• Matrix Subspace Conjugacy

• Permutation Group Conjugacy

• Code Equivalence

• GI

Is Graph Automorphism in ZPPMCSP?

• Is Graph Automorphism in ZPPMCSP?

• Is there some way to relate the complexities of MKTP and (the many versions of) MCSP?

• …through Gap Amplification, or via some other means?

• MKTP is not in AC0[p] for any prime p. How about MCSP?

Input: (G0,G1): Isomorphic Graphs. Repeat 100 times:

• Input: (G0,G1): Isomorphic Graphs. Repeat 100 times:

• Prover: Picks a random isomorphic copy H of G0, (and G1).

• Verifier: Picks b in {0,1} at random.

• Prover: Gives an isomorphism between Gb and H.

• The Verifier doesn’t learn an isomorphism between G0 and G1. The Verifier learns NOTHING!