# Nycac 2015: Graph Automorphism and Circuit Size

Yüklə 0,55 Mb.
 tarix 28.06.2018 ölçüsü 0,55 Mb. #52234

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

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

• ## 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.

• ## 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.

• ## 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.

• ## 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}

• ## 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)

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

Yüklə 0,55 Mb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023
rəhbərliyinə müraciət

Ana səhifə