Classical algorithms from quantum and Arthur-Merlin communication protocols

DOI10.4230/LIPICS.ITCS.2019.23MaRDI QIDQ5090396zbMATH OpenFDO

Authors Lijie Chen, Ruosong Wang

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1811.07515

zbMATH Keywords

approximate countingapproximate rankquantum communication protocolsArthur-Merlin communication protocols

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The pattern matrix method
• Quantum lower bounds for approximate counting via Laurent polynomials
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• The layer complexity of Arthur-Merlin-like communication

Cites work

• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• An invariance principle for polytopes
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Beating brute force for systems of polynomial equations over finite fields
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Faster all-pairs shortest paths via circuit complexity
• Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Improving exhaustive search implies superpolynomial lower bounds
• Lower bounds in communication complexity
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• More applications of the polynomial method to algorithm design
• Nonuniform ACC circuit lower bounds
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• On the parameterized complexity of approximating dominating set
• Optimal succinct rank data structure via approximate nonnegative tensor decomposition
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Probabilistic communication complexity
• Probabilistic rank and matrix rigidity
• Quantum Walk Algorithm for Element Distinctness
• Quantum search of spatial regions
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Reflections for quantum query algorithms
• Relative error tensor low rank approximation
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• The Quantum Communication Complexity of Sampling
• The approximate rank of a matrix and its algorithmic applications
• The cover number of a matrix and its algorithmic applications
• The landscape of communication complexity classes
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Tighter connections between Formula-SAT and shaving logs
• Zero-information protocols and unambiguity in Arthur-Merlin communication

Cited in

(5)

• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Predicate encryption from bilinear maps and one-sided probabilistic rank
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms

This page was built for publication: Classical algorithms from quantum and Arthur-Merlin communication protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090396)