What Circuit Classes Can Be Learned with Non-Trivial Savings?
From MaRDI portal
Publication:4638080
DOI10.4230/LIPIcs.ITCS.2017.30zbMath1402.68112OpenAlexW2773065828MaRDI QIDQ4638080
Li-Yang Tan, Rocco A. Servedio
Publication date: 3 May 2018
Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.30
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Fooling Polytopes ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
Cites Work
- The correct exponent for the Gotsman-Linial conjecture
- Learning intersections and thresholds of halfspaces
- Exact exponential algorithms.
- Boolean function complexity. Advances and frontiers.
- Learning regular sets from queries and counterexamples
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Queries and concept learning
- Mining circuit lower bound proofs for meta-algorithms
- On PAC learning algorithms for rich Boolean function classes
- Exact learning Boolean functions via the monotone theory
- Improving exhaustive search implies superpolynomial lower bounds
- Constant depth circuits, Fourier transform, and learnability
- Learnability and the Vapnik-Chervonenkis dimension
- An improved exponential-time algorithm for k -SAT
- Learning and Lower Bounds for AC 0 with Threshold Gates
- A theory of the learnable
- On Learning Ring-Sum-Expansions
- Learning Integer Lattices
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- On the Correlation of Parity and Small-Depth Circuits
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Learning algorithms from natural proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: What Circuit Classes Can Be Learned with Non-Trivial Savings?
