scientific article; zbMATH DE number 7250145
From MaRDI portal
Publication:5121893
DOI10.4230/LIPIcs.CCC.2018.5zbMath1441.68074MaRDI QIDQ5121893
Igor C. Oliveira, Rahul Santhanam, Shuichi Hirahara
Publication date: 22 September 2020
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
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for depth-3 circuits with MOD \(m\) gates
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Boolean function complexity. Advances and frontiers.
- Approximating probability distributions using small sample spaces
- Exponential lower bounds for depth three Boolean circuits
- The Complexity of DNF of Parities
- Zero Knowledge and Circuit Minimization
- The Minimum Oracle Circuit Size Problem.
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A threshold of ln n for approximating set cover
- Circuit minimization problem
- On Graph Complexity
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Computational limitations on learning from examples
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Reducibility among Combinatorial Problems
- Pseudorandom Functions: Three Decades Later
- Linear Systems over Composite Moduli
- Non-approximability results for optimization problems on bounded degree instances
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Learning algorithms from natural proofs
- Power from Random Strings
- Natural proofs
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
