Improved Merlin-Arthur Protocols for Fine-Grained Complexity Problems
The text discusses Merlin-Arthur proof systems and protocols for central problems in fine-grained complexity, particularly focusing on the time complexity, completeness, and soundness of these protocols. It also touches on recent interest in these protocols and presents new results in areas such as Orthogonal Vectors Problem, 3SUM, and All-Pairs Shortest Paths (APSP). The work highlights the near-optimal MA protocols developed for these complex problems.
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
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity Shyan Akmal MIT Lijie Chen MIT Malvika Raj UC Berkeley Ryan Williams MIT Ce Jin MIT ITCS 2022
Merlin-Arthur Proof Systems Arthur wants Merlin to evaluate a function ?:{0,1} {0,1} for him On input ? {0,1}?, Merlin needs to convince Arthur that ? ? = ?. sends answer ? and proof? of length ?(?) Prover (Merlin) Verifier (Arthur) runs (randomized) ?(?,?,?) in ?(?) time (on word-RAM) Completeness: If ? ? = ?, then exists ? such that ?(?,?,?) accepts with probability 1. Soundness: If ? ? ?, then for all ?, ? ?,?,? rejects with probability 2/3. The Merlin-Arthur time of this protocol is ? ? + ?(?). Non-deterministic algorithm: rejects with probability 1
Fine-grained Complexity Recent interest in Merlin-Arthur protocols for central problems in fine-grained complexity (from Vassilevska Williams 15)
Williams MA protocol for Orthogonal Vectors OV Problem: Let ? = ?(log?); given ?,? 0,1?with ? = ? = ?, determine if there is an OV pair ? ?,? ? so that ?,? 1 ? ??? ??= 0. Best known algorithms need ?2 ? 1 time [Abboud-Williams-Yu 15, Chan-Williams 16] [Williams CCC 16]: Counting OV pairs can be done in ?(??) MA time. Near-optimal time Nearly quadratic speedup (refuting MASETH) Williams results led to many subsequent works: [Bj rklund-Kaski 16]: MA Protocols for #k-Clique, Graph Coloring, Set Cover, ... Further work in fine-grained cryptography and average-case fine-grained complexity [BRSV 18, ] Question: Are there fast MA protocols for other problems in fine-grained complexity? This work: Near-optimal MA protocols for 3SUM and APSP (and many more )
New Results 3-SUM, (min,+)-convolution, Subset Sum Counting Zero-weight Cliques, APSP ?-Unsatisfiability Quantified Boolean Formula
Result 1: ?-SUM ?-SUM Problem (for fixed integer ? 3): Given ? integers, decide if there exist ? of them that sum to zero. Best known algorithm for 3-SUM runs in ?2 ?(1) time for ?-SUM: ??/2 ?(1)time Theorem: Certifying that no ?-SUM solution exists can be done in MA time ? ??/3. NO 3-SUM can be certified in ?(?) MA time (near-optimal). Previously known [Carmosino-Gao-Impagliazzo-Mihajlin-Paturi-Schneider 16]: NO 3-SUM can be certified in ?(?1.5) Nondeterministic time. ? hides polylog(?) factors
Implications of the 3-SUM protocol Subset Sum Problem: Given ? integers and a target ?, decide if there exists a subset of them that sums to ?. Best known algorithm runs in ?(2?/2) time [Horowitz-Sahni 74] Theorem: NO Subset Sum can be certified in ? (2?/3) MA time. Previous result [Nederlof 17]: NO Subset Sum in ? (20.49991?) MA Time. (min,+)-convolution: Given integers ?1, ,?? and ?1, ,??, compute ??= min 1 ?<?{??+ ?? ?} for all ?. Using the techniques from [Vassilevska-Williams 09], we obtain: Theorem: (min,+)-convolution can be computed in ?(?) MA time. ? hides poly(?) factors
Result 2: Counting Cliques Previous results for Counting ?-cliques in a ?-vertex graph (for fixed integer ? 3): [Williams 16]: ? ??/2 +2 MA time [Bj rklund-Kaski 16]: ? ???/6 MA time (for ? divisible by 6). [Goldreich-Rothblum 17]: ? ??/2 MA time (nearly quadratic speedup) #ZeroWeight-?-clique: Given a simple undirected graph (with ? vertices and ? edges) with integer edge weights, count the number of ?-cliques with zero total weight. Theorem: #ZW-?-Clique can be solved in MA time ?(? ?/2 ). #ZW-4-Clique in MA time ?(?2) Further improvement for odd ? on sparse graphs e.g., #ZW-Triangle in ?(?) MA time with ?(?) proof length Implications: APSP (and (min,+)-product) can be solved in ?(?2) MA time Previously known [CGIMPS 16]: APSP in ? ??.?? Non-deterministic time
Result 3: ?-UNSAT Input: an ?-variable ?-clause ?-CNF Example: ?1 ?2 ?3 ?2 ?4 ?5 is a (satisfiable) 3-CNF Best known algorithms for ?-CNF-SAT runs in ? (2? ??/?) time (for some constant ?) Theorem: Certifying that the ?-CNF is unsatisfiable can be done in ? (2?/2 ? ?/?) MA time (for some constant ? ) Previously known: #SAT in ? (2?/2) MA time [Williams 16] Remark: Williams protocol algebrizes (in the sense of [Aaronson-Wigderson 09]). There is NO algebrizing protocol for ?-UNSAT in 2?/2/??(1) time. Therefore we have to exploit non-algebrizing properties in our ?-UNSAT protocol. ? hides poly(?,?) factors
Result 4: Quantified Boolean Formula Given a Quantified Boolean Formula in prenex normal form, ?1?1 (????) ?(?1,...,??) where ?? { , } and ? is a formula of size ?, decide whether it is a True QBF. PSPACE-complete problem with an ? (2?) time algorithm [Williams 16] gave a 3-round (AMA) protocol in ? (22?/3) time Open question [Williams 16]: Is there an MA protocol in ? (21 ? ?) time? Theorem: True QBF can be certified in ? (24?/5) MA time. ? hides poly(?,?) factors
3-SUM, (min,+)-convolution, Subset Sum This talk Counting Zero-weight Cliques, APSP ?-Unsatisfiability Quantified Boolean Formula
NO-3-SUM Input integers ?1, ,??. A 3-SUM solution: ?,?,? ?3 such that ??+ ??+ ??= 0 (repeated indices allowed) Task: Certify that no 3-SUM solution exists, in ?(?) MA time.
Step 1: NO-3-SUM #3-SUM with small input range Input integers ?1, ,??. A 3-SUM solution: ?,?,? ?3 such that ??+ ??+ ??= 0 (repeated indices allowed) Task: Certify that no 3-SUM solution exists, in ?(?) MA time. Idea from [CGIMPS 16]: Pick a positive integer integer ?, A relaxed 3-SUM solution: ?,?,? ?3such that ??+ ??+ ?? 0 (??? ?) Exists ? ?2 such that there are at most ? ? relaxed solutions. Sends ? ?2 and the list { ?1,?1,?1, ,(??,??,??)} of all ? ?(?) relaxed solutions Prover Verifier Checks: (1) The 3-tuples in the list are distinct relaxed solutions (2) None of the relaxed solutions are real solutions (3) The input has exactly ? relaxed solutions New task: Given input integers ?1, ,?? {?,?, ,?} (where ? ?2),prove that the number of tuples ?,?,? ?3 such that ??+ ??+ ??= ? is ??. where ? {?,2?,3?}, and ? = ??+ ?2?+ ?3?
Step 2: Verifying Polynomial Coefficients = ?? Given integers ?1, ,?? {1,2, ,?2}, prove that the number of tuples ?,?,? ?3 such that ??+ ??+ ??= ? is ??. Define degree-?2 polynomial ? ? ? [?]???, and let ? ?3= 1 ? 3?2 ???? Inspired by [Nederlof 17], let ? = { 1 ? 3?2 | ? ? mod ? } Merlin sends {??}? ?and claims ??= ?? for all ? ?. Arthur picks random ? ??, and checks ? ?????= ? ????? Failure probability 3?2/?, by Schwartz-Zippel Lemma ? ? and ? ???/? = ?(?)
Step 2: Verifying Polynomial Coefficients (contd) = ?? Given integers ?1, ,?? {1,2, ,?2}, prove that the number of tuples ?,?,? ?3 such that ??+ ??+ ??= ? is ??. Define degree-?2 polynomial ? ? ? [?]???, and let ? ?3= 1 ? 3?2 ???? Inspired by [Nederlof 17], let ? = { 1 ? 3?2 | ? ? mod ? } How to evaluate ? ?????? Note that ? ??3= 1 ? 3?2 ?????? ? ??3mod (?? 1) = 1 ? 3?2 ?????? mod ? ? ? and ? ???/? = ?(?) ? ????? equals the ?? mod ? term coefficient of ? ??3 mod (?? 1) = (? ?? mod ?? 1 )3mod ?? 1 =( ? [?]??? ??? mod ?)3mod ?? 1 Total MA time = ? |?| + ? ?(?) Computable in ?(?) time using FFT
Open problems Can we certify NO Subset Sum in ? (2?/4) MA time? We achieved ? (2?/3) Can we certify True QBF in ? (2?/2) MA time? We achieved ? (24?/5) Thanks!
