Ján Pich
YOU?
Author Swipe
View article: Learning algorithms from circuit lower bounds
Learning algorithms from circuit lower bounds Open
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small…
View article: Localizability of the approximation method
Localizability of the approximation method Open
We use the approximation method of Razborov to analyze the locality barrier which arose from the investigation of the hardness magnification approach to complexity lower bounds. Adapting a limitation of the approximation method obtained by…
View article: From Proof Complexity to Circuit Complexity via Interactive Protocols
From Proof Complexity to Circuit Complexity via Interactive Protocols Open
Folklore in complexity theory suspects that circuit lower bounds against NC¹ or P/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishin…
View article: From Proof Complexity to Circuit Complexity via Interactive Protocols
From Proof Complexity to Circuit Complexity via Interactive Protocols Open
Folklore in complexity theory suspects that circuit lower bounds against NC¹ or P/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishin…
View article: Towards P$\ne$NP from Extended Frege lower bounds
Towards P$\ne$NP from Extended Frege lower bounds Open
We prove that if conditions I-II (below) hold and there is a sequence of Boolean functions $f_n$ hard to approximate by p-size circuits such that p-size circuit lower bounds for $f_n$ do not have p-size proofs in Extended Frege system EF, …
View article: Localizability of the approximation method
Localizability of the approximation method Open
We use the approximation method of Razborov to analyze the locality barrier which arose from the investigation of the hardness magnification approach to complexity lower bounds. Adapting a limitation of the approximation method obtained by…
View article: Learning Algorithms Versus Automatability of Frege Systems
Learning Algorithms Versus Automatability of Frege Systems Open
We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system P, we prove that the following statements are equivalent, - Provab…
View article: Learning algorithms from circuit lower bounds
Learning algorithms from circuit lower bounds Open
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small…
View article: Frege Systems for Quantified Boolean Logic
Frege Systems for Quantified Boolean Logic Open
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating…
View article: Beyond Natural Proofs: Hardness Magnification and Locality
Beyond Natural Proofs: Hardness Magnification and Locality Open
Hardness magnification reduces major complexity separations (such as EXP ⊈ NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M…
View article: Beyond Natural Proofs: Hardness Magnification and Locality
Beyond Natural Proofs: Hardness Magnification and Locality Open
Hardness magnification reduces major complexity separations (such as $\mathsf{\mathsf{EXP}} \nsubseteq \mathsf{NC}^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT1…
View article: Hardness Magnification near State-Of-The-Art Lower Bounds
Hardness Magnification near State-Of-The-Art Lower Bounds Open
This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be s…
View article: Hardness magnification near state-of-the-art lower bounds.
Hardness magnification near state-of-the-art lower bounds. Open
This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be s…
View article: Reasons for Hardness in QBF Proof Systems
Reasons for Hardness in QBF Proof Systems Open
We aim to understand inherent reasons for lower bounds for QBF proof systems, and revisit and compare two previous approaches in this direction. The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bou…
View article: Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic Open
We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this theorem was known). This includes a formalization of the exis…