Ján Pich

According to our database, Ján Pich authored at least 16 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Localizability of the approximation method.

Ján Pich

Comput. Complex., December, 2024

From Proof Complexity to Circuit Complexity via Interactive Protocols.

Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Towards P $\neq$ NP from Extended Frege Lower Bounds.

Ján Pich, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2023

2022

Learning Algorithms Versus Automatability of Frege Systems.

Ján Pich, Rahul Santhanam

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly.

Ján Pich, Rahul Santhanam

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Frege Systems for Quantified Boolean Logic.

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, Ján Pich

J. ACM, 2020

Learning algorithms from circuit lower bounds.

Ján Pich

CoRR, 2020

2019

Beyond Natural Proofs: Hardness Magnification and Locality.

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2019

Why are Proof Complexity Lower Bounds Hard?

Ján Pich, Rahul Santhanam

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Hardness magnification near state-of-the-art lower bounds.

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2018

2017

Feasibly constructive proofs of succinct weak circuit lower bounds.

Moritz Müller, Ján Pich

Electron. Colloquium Comput. Complex., 2017

Reasons for Hardness in QBF Proof Systems.

Olaf Beyersdorff, Luke Hinde, Ján Pich

Electron. Colloquium Comput. Complex., 2017

2016

Understanding Gentzen and Frege systems for QBF.

Olaf Beyersdorff, Ján Pich

Electron. Colloquium Comput. Complex., 2016

2015

Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic.

Ján Pich

Log. Methods Comput. Sci., 2015

2013

Circuit Lower Bounds in Bounded Arithmetics.

Ján Pich

Electron. Colloquium Comput. Complex., 2013

2010

Nisan-Wigderson generators in proof systems with forms of interpolation.

Ján Pich

Electron. Colloquium Comput. Complex., 2010