Classical algorithms from quantum and Arthur-Merlin communication protocols

DOI10.4230/LIPICS.ITCS.2019.23MaRDI QIDQ5090396FDOQ5090396

Authors: Lijie Chen, Ruosong Wang 

Publication date: 18 July 2022

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

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

zbMATH Keywords

approximate countingapproximate rankquantum communication protocolsArthur-Merlin communication protocols

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)