Adversary lower bound for the k-sum problem
From MaRDI portal
Publication:2986881
DOI10.1145/2422436.2422474zbMath1361.68092arXiv1206.6528OpenAlexW2113364475MaRDI QIDQ2986881
Robert Špalek, Aleksandrs Belovs
Publication date: 16 May 2017
Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.6528
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Optimal parallel quantum query algorithms, Algorithmic Polynomials, On the power of non-adaptive learning graphs, Unnamed Item, Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems, Unnamed Item, Key establishment à la Merkle in a quantum world, Unnamed Item, Unnamed Item, Attacks on beyond-birthday-bound MACs in the quantum setting, Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Teachability in computational learning
- Measuring teachability using variants of the teaching dimension
- Teaching a smarter learner.
- Occam's razor
- Pseudorandom generators for space-bounded computation
- On the power of inductive inference from good examples
- A model of interactive teaching
- Learning from different teachers
- On the limits of efficient teachability
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- On the complexity of teaching
- On specifying Boolean functions by labelled examples
- Recent Developments in Algorithmic Teaching
- A theory of the learnable
- Teaching Randomized Learners
- Algorithmic Learning Theory
- A theory of goal-oriented communication
- Derandomizing polynomial identity tests means proving circuit lower bounds
