scientific article; zbMATH DE number 7204269

DOI10.4230/LIPIcs.CCC.2017.18zbMath1440.68083arXiv1611.01190MaRDI QIDQ5111148

Rahul Santhanam, Igor C. Oliveira

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1611.01190

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

learning theoryBoolean circuitspseudorandomness

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (19)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ The power of natural properties as oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Unnamed Item ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Quantum Hardness of Learning Shallow Classical Circuits

This page was built for publication: