scientific article; zbMATH DE number 7250146
From MaRDI portal
Publication:5121894
DOI10.4230/LIPIcs.CCC.2018.6zbMath1441.68047arXiv1802.09121MaRDI QIDQ5121894
Publication date: 22 September 2020
Full work available at URL: https://arxiv.org/abs/1802.09121
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (6)
Weights of exact threshold functions ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ 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 ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Estimation of certain exponential sums arising in complexity theory
- A Turing machine time hierarchy
- Exact exponential algorithms.
- On the power of small-depth threshold circuits
- On the correlation between parity and modular polynomials
- Non-uniform automata over groups
- On ACC
- The correlation between parity and quadratic polynomials mod \(3\)
- Threshold circuits of bounded depth
- Theory of majority decision elements
- Finding, Minimizing, and Counting Weighted Subgraphs
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Nonuniform ACC Circuit Lower Bounds
- PP is as Hard as the Polynomial-Time Hierarchy
- Local Reductions
- Set Partitioning via Inclusion-Exclusion
- Circuit Lower Bounds for Merlin–Arthur Classes
- Weights of Exact Threshold Functions
- Computing Partitions with Applications to the Knapsack Problem
- Separating Nondeterministic Time Complexity Classes
- Lower bounds on threshold and related circuits via communication complexity
- Bounds for the Computational Power and Learning Complexity of Analog Neural Nets
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Beating Brute Force for Systems of Polynomial Equations over Finite Fields
- New algorithms and lower bounds for circuits with linear threshold gates
- On the correlation of symmetric functions
- Short PCPs with Projection Queries
- Counting Solutions to Polynomial Systems via Reductions
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
This page was built for publication:
