Quantum hardness of learning shallow classical circuits
From MaRDI portal
Publication:4994987
Recommendations
- Equivalences and Separations Between Quantum and Classical Learnability
- scientific article; zbMATH DE number 1754656
- Quantum algorithms and approximating polynomials for composed functions with shared inputs
- Cryptographic hardness for learning intersections of halfspaces
- Improved bounds on quantum learning algorithms
Cites work
- (Gap/S)ETH hardness of SVP
- A decade of lattice cryptography
- A Simple Unpredictable Pseudo-Random Number Generator
- A theory of the learnable
- A toolkit for ring-LWE cryptography
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- BKZ 2.0: Better lattice security estimates
- Classical hardness of learning with errors
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- Constant depth circuits, Fourier transform, and learnability
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- Cryptographic hardness for learning intersections of halfspaces
- Cryptographic hardness of distribution-specific learning
- Cryptographic limitations on learning Boolean formulae and finite automata
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Factoring polynomials with rational coefficients
- scientific article; zbMATH DE number 1942427 (Why is no real title available?)
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
- Majority gates vs. general weighted threshold gates
- New Algorithms for Learning in Presence of Errors
- Noise-tolerant learning, the parity problem, and the statistical query model
- Number-theoretic constructions of efficient pseudo-random functions
- On ideal lattices and learning with errors over rings
- On lattices, learning with errors, random linear codes, and cryptography
- On the limits of nonapproximability of lattice problems
- On Threshold Circuits and Polynomial Computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Pseudorandom functions and lattices
- Pseudorandomness of ring-LWE for any ring and modulus
- Public-key cryptosystems from the worst-case shortest vector problem
- Quantum algorithms for learning and testing juntas
- Quantum Complexity Theory
- Quantum information complexity
- Queries and concept learning
- Random oracles in a quantum world
- SETH-based lower bounds for subset sum and bicriteria path
- Supervised learning with quantum computers
- Threshold circuits of small majority-depth
- Two new results about quantum exact learning
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Worst-case to average-case reductions for module lattices
Cited in
(4)- Quantum learning Boolean linear functions w.r.t. product distributions
- scientific article; zbMATH DE number 1754656 (Why is no real title available?)
- Equivalences and Separations Between Quantum and Classical Learnability
- The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems
This page was built for publication: Quantum hardness of learning shallow classical circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994987)
