scientific article; zbMATH DE number 7559066
From MaRDI portal
Publication:5090396
DOI10.4230/LIPIcs.ITCS.2019.23MaRDI QIDQ5090396
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1811.07515
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
approximate countingapproximate rankquantum communication protocolsArthur-Merlin communication protocols
Related Items (4)
Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Probabilistic communication complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The landscape of communication complexity classes
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- The Cover Number of a Matrix and its Algorithmic Applications
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- Nonuniform ACC Circuit Lower Bounds
- Lower Bounds in Communication Complexity
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- The Quantum Communication Complexity of Sampling
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Beating Brute Force for Systems of Polynomial Equations over Finite Fields
- Probabilistic rank and matrix rigidity
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
- Optimal succinct rank data structure via approximate nonnegative tensor decomposition
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- On the parameterized complexity of approximating dominating set
- Fine-grained Complexity Meets IP = PSPACE
- Relative Error Tensor Low Rank Approximation
- Faster all-pairs shortest paths via circuit complexity
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- More Applications of the Polynomial Method to Algorithm Design
- An invariance principle for polytopes
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Quantum Walk Algorithm for Element Distinctness
- The approximate rank of a matrix and its algorithmic applications
This page was built for publication:
