Ján Pich

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

Collaborative distances:

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

2025

Learning algorithms from circuit lower bounds.

Ján Pich

Comput. Complex., June, 2025

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

Beyond Natural Proofs: Hardness Magnification and Locality.

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

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

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

Hardness Magnification near State-Of-The-Art Lower Bounds.

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Proceedings of the 34th Computational Complexity Conference, 2019

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

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Understanding Gentzen and Frege Systems for QBF.

Olaf Beyersdorff, Ján Pich

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 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

2011

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

Ján Pich

Math. Log. Q., 2011