New algorithms and lower bounds for circuits with linear threshold gates
From MaRDI portal
DOI10.4086/toc.2018.v014a017zbMath1410.68127arXiv1401.2444OpenAlexW2905428333MaRDI QIDQ4612481
Publication date: 31 January 2019
Published in: Theory of Computing, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.2444
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (24)
Local Reductions ⋮ Local reduction ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ On polynomial approximations to AC ⋮ Depth Reduction for Composites ⋮ Unnamed Item ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Unnamed Item ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Average-case rigidity lower bounds ⋮ Upper bound for torus polynomials ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of a threshold gate at the top
- Exponential lower bound for bounded depth circuits with few threshold gates
- A Turing machine time hierarchy
- Computing dominances in \(E^ n\)
- Threshold circuits of small majority-depth
- The expressive power of voting polynomials
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Complex polynomials and circuit lower bounds for modular counting
- On ACC
- Efficient threshold circuits for power series
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Efficient algorithms for privately releasing marginals via convex relaxations
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Threshold circuits of bounded depth
- Polynomial threshold functions and Boolean threshold circuits
- Theory of majority decision elements
- Natural Proofs versus Derandomization
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- The Sign-Rank of AC$^0$
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
- Number-theoretic constructions of efficient pseudo-random functions
- Nonuniform ACC Circuit Lower Bounds
- Constant Depth Reducibility
- Complexity Lower Bounds using Linear Algebra
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Learning and Lower Bounds for AC 0 with Threshold Gates
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Rapid Multiplication of Rectangular Matrices
- On Threshold Circuits and Polynomial Computation
- Depth efficient neural networks for division and related problems
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Collusion-secure fingerprinting for digital data
- On small depth threshold circuits
- Short PCPs with Projection Queries
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Automata, Languages and Programming
- Theory of Cryptography
- Natural proofs
This page was built for publication: New algorithms and lower bounds for circuits with linear threshold gates
