scientific article; zbMATH DE number 7561750
From MaRDI portal
Publication:5092472
DOI10.4230/LIPIcs.CCC.2020.22MaRDI QIDQ5092472
Rahul Ilango, Igor C. Oliveira, Bruno Loff
Publication date: 21 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (6)
The power of natural properties as oracles ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ OR-Toffoli and OR-Peres Reversible Gates ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
Cites Work
- Boolean function complexity. Advances and frontiers.
- Occam's razor
- Zero knowledge and the chromatic number
- Graph complexity
- Lower bounds on learning decision lists and trees
- Feasibly constructive proofs of succinct weak circuit lower bounds
- The minimum oracle circuit size problem
- The complexity of properly learning simple concept classes
- The Complexity of DNF of Parities
- Improved Hardness of Approximating Chromatic Number
- Zero Knowledge and Circuit Minimization
- Linear degree extractors and the inapproximability of max clique and chromatic number
- A threshold of ln n for approximating set cover
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Circuit minimization problem
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- On the Shortest Linear Straight-Line Program for Computing Linear Forms
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Computational limitations on learning from examples
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Cryptographic limitations on learning Boolean formulae and finite automata
- On the hardness of approximating minimization problems
- Communication Lower Bounds via Critical Block Sensitivity
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Hardness magnification near state-of-the-art lower bounds
- Improved hardness for H-colourings of G-colourable graphs
- On the complexity of communication complexity
- Non-approximability results for optimization problems on bounded degree instances
- The log-approximate-rank conjecture is false
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Learning algorithms from natural proofs
- Natural proofs
- The non-hardness of approximating circuit size
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
