Publication:4612481

DOI10.4086/toc.2018.v014a017zbMath1410.68127arXiv1401.2444OpenAlexW2905428333MaRDI QIDQ4612481

R. Ryan Williams

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

zbMATH Keywords

circuit complexitylinear threshold functionssatisfiability algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

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

• SuLQ

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