Quantum Hardness of Learning Shallow Classical Circuits
From MaRDI portal
Publication:4994987
DOI10.1137/20M1344202OpenAlexW2963234912MaRDI QIDQ4994987
Alex Bredariol Grilo, Aarthi Sundaram, Srinivasan Arunachalam
Publication date: 22 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.02840
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Factoring polynomials with rational coefficients
- Majority gates vs. general weighted threshold gates
- Threshold circuits of small majority-depth
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- On the limits of nonapproximability of lattice problems
- Supervised learning with quantum computers
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Queries and concept learning
- Worst-case to average-case reductions for module lattices
- Quantum algorithms for learning and testing juntas
- Cryptographic hardness for learning intersections of halfspaces
- A Decade of Lattice Cryptography
- Pseudorandom Functions and Lattices
- Quantum Information Complexity
- New Algorithms for Learning in Presence of Errors
- BKZ 2.0: Better Lattice Security Estimates
- Random Oracles in a Quantum World
- Constant depth circuits, Fourier transform, and learnability
- Number-theoretic constructions of efficient pseudo-random functions
- A theory of the learnable
- A Simple Unpredictable Pseudo-Random Number Generator
- On Threshold Circuits and Polynomial Computation
- Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
- Cryptographic limitations on learning Boolean formulae and finite automata
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Complexity Theory
- A Toolkit for Ring-LWE Cryptography
- Pseudorandomness of ring-LWE for any ring and modulus
- Public-key cryptosystems from the worst-case shortest vector problem
- (Gap/S)ETH hardness of SVP
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Cryptographic hardness of distribution-specific learning
- On Ideal Lattices and Learning with Errors over Rings
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- Classical hardness of learning with errors
- On lattices, learning with errors, random linear codes, and cryptography
- Noise-tolerant learning, the parity problem, and the statistical query model
This page was built for publication: Quantum Hardness of Learning Shallow Classical Circuits
