Cryptographic hardness for learning intersections of halfspaces
From MaRDI portal
Publication:2517820
DOI10.1016/j.jcss.2008.07.008zbMath1158.68384OpenAlexW2119877753MaRDI QIDQ2517820
Adam R. Klivans, Alexander A. Sherstov
Publication date: 9 January 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.07.008
computational learning theoryintersections of halfspacesLattice-based cryptographycryptographic hardness results
Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25)
Related Items (18)
Fast Pseudorandom Functions Based on Expander Graphs ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Fooling Polytopes ⋮ Complexity of training ReLU neural network ⋮ On the hardness of learning intersections of two halfspaces ⋮ Polynomial‐time universality and limitations of deep learning ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Convergence Results for Neural Networks via Electrodynamics ⋮ The hardest halfspace ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability
Cites Work
- Unnamed Item
- Learning intersections and thresholds of halfspaces
- Learning sparse multivariate polynomials over a field with queries and counterexamples.
- Unconditional lower bounds for learning intersections of halfspaces
- Majority gates vs. general weighted threshold gates
- PAC learning intersections of halfspaces with membership queries
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Learning intersections of halfspaces with a margin
- Parity, circuits, and the polynomial-time hierarchy
- Lattice problems in NP ∩ coNP
- On Agnostic Learning of Parities, Monomials, and Halfspaces
- A theory of the learnable
- A Simple Unpredictable Pseudo-Random Number Generator
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Cryptographic limitations on learning Boolean formulae and finite automata
- Simulating Threshold Circuits by Majority Circuits
- Learning functions represented as multiplicity automata
- Randomized Interpolation and Approximation of Sparse Polynomials
- Randomness efficient identity testing of multivariate polynomials
- Cryptographic hardness of distribution-specific learning
- Learning Theory and Kernel Machines
- New lattice-based cryptographic constructions
- Lattice-Based Cryptography
- On lattices, learning with errors, random linear codes, and cryptography
This page was built for publication: Cryptographic hardness for learning intersections of halfspaces
