Search results
- 1.0588526 - MÚ 2025 RIV DE eng C - Conference Paper (international conference)
Gurumukhani, M. - Paturi, R. - Pudlák, Pavel - Saks, M. - Talebanfard, Navid
Local enumeration and majority lower bounds.
39th Computational Complexity Conference (CCC 2024). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2024 - (Santhanam, S.), č. článku 17. Leibniz International Proceedings in Informatics, 300. ISBN 978-3-95977-331-7. E-ISSN 1868-8969.
[39th Computational Complexity Conference (CCC 2024). Ann Arbor (US), 22.07.2024-25.07.2024]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : circuit lower bounds * depth 3 circuits * k-CNF satisfiability * majority function
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.4230/LIPIcs.CCC.2024.17
Permanent Link: https://hdl.handle.net/11104/0355395File Download Size Commentary Version Access Pudlak.pdf 0 912.7 KB Publisher’s postprint open-access - 2.0579481 - MÚ 2024 RIV CH eng C - Conference Paper (international conference)
Dvořák, P. - Folwarczný, Lukáš - Opler, M. - Pudlák, Pavel - Šámal, R. - Vu, T.
Bounds on functionality and symmetric difference - two intriguing graph parameters.
Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023 - (Paulusma, D.; Ries, B.), s. 305-318. Lecture Notes in Computer Science, 14093. ISBN 978-3-031-43379-5. ISSN 0302-9743.
[49th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2023. Fribourg (CH), 28.06.2023-30.06.2023]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : finite projective plane * functionality * intersection graphs * symmetric difference
OECD category: Pure mathematics
https://doi.org/10.1007/978-3-031-43380-1_22
Permanent Link: https://hdl.handle.net/11104/0348321File Download Size Commentary Version Access Folwarczny3.pdf 0 247.8 KB Publisher’s postprint require - 3.0559512 - MÚ 2023 RIV DE eng C - Conference Paper (international conference)
Gryaznov, Svyatoslav - Pudlák, Pavel - Talebanfard, Navid
Linear branching programs and directional affine extractors.
37th Computational Complexity Conference (CCC 2022). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2022 - (Lovett, S.), s. 1-16, č. článku 4. Leibniz International Proceedings in Informatics, 234. ISBN 978-3-95977-241-9. ISSN 1868-8969.
[37th Computational Complexity Conference (CCC 2022). Philadelphia (US), 20.07.2022-23.07.2022]
R&D Projects: GA ČR(CZ) GX19-27871X; GA ČR(CZ) GA19-05497S
Institutional support: RVO:67985840
Keywords : Boolean functions * average-case lower bounds * affine dispersers * affine extractors
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.4230/LIPIcs.CCC.2022.4
Permanent Link: https://hdl.handle.net/11104/0332788File Download Size Commentary Version Access Gryaznov.pdf 2 696.6 KB Publisher’s postprint open-access - 4.0489223 - MÚ 2019 RIV US eng C - Conference Paper (international conference)
Lokshtanov, D. - Mikhailin, I. - Ramamohan, P. - Pudlák, Pavel
Beating brute force for (quantified) satisfiability of circuits of bounded treewidth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2018 - (Czumaj, A.), s. 247-261. ISBN 978-1-61197-503-1.
[Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). New Orleans (US), 07.01.2018-10.01.2018]
Institutional support: RVO:67985840
Keywords : algorithmic properties of circuits of bounded treewidth
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.18
Permanent Link: http://hdl.handle.net/11104/0283675File Download Size Commentary Version Access Pudlak.pdf 2 624.9 KB Publisher’s postprint require - 5.0483703 - MÚ 2018 RIV US eng C - Conference Paper (international conference)
Hrubeš, Pavel - Pudlák, Pavel
Random formulas, monotone circuits, and interpolation.
2017 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). New York: IEEE, 2017, s. 121-131. Annual IEEE Symposium on Foundations of Computer Science. ISBN 978-1-5386-3464-6. ISSN 0272-5428.
[58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). Berkeley (US), 15.10.2017-17.10.2017]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : Cutting Planes * random formulas * interpolation
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://ieeexplore.ieee.org/document/8104052/
Permanent Link: http://hdl.handle.net/11104/0278908File Download Size Commentary Version Access Hrubes.pdf 11 296.4 KB Publisher’s postprint require - 6.0477105 - MÚ 2018 RIV DE eng C - Conference Paper (international conference)
Pudlák, Pavel - de Oliveira Oliveira, Mateus
Representations of monotone Boolean functions by linear programs.
32nd Computational Complexity Conference (CCC 2017). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 - (O’Donnell, R.), s. 1-14, č. článku 3. Leibniz International Proceedings in Informatics, 79. ISBN 978-3-95977-040-8. ISSN 1868-8969.
[32nd Computational Complexity Conference (CCC 2017). Riga (LT), 06.07.2017-09.07.2017]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : Monotone Linear Programming Circuits * Lovász-Schrijver Proof System * Cutting-Planes Proof System
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/volltexte/2017/7520
Permanent Link: http://hdl.handle.net/11104/0273491File Download Size Commentary Version Access DeOliveiraOliveira2.pdf 2 534.9 KB Publisher’s postprint require - 7.0477098 - MÚ 2018 RIV DE eng C - Conference Paper (international conference)
Pudlák, Pavel - Thapen, Neil
Random resolution refutations.
32nd Computational Complexity Conference (CCC 2017). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 - (O’Donnell, R.), s. 1-10, č. článku 1. Leibniz International Proceedings in Informatics, 79. ISBN 978-3-95977-040-8. ISSN 1868-8969.
[32nd Computational Complexity Conference (CCC 2017). Riga (LT), 06.07.2017-09.07.2017]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : proof complexity * random * resolution * resolution
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/volltexte/2017/7523
Permanent Link: http://hdl.handle.net/11104/0273490File Download Size Commentary Version Access Pudlak3.pdf 3 538.1 KB Publisher’s postprint require - 8.0476174 - MÚ 2018 RIV DE eng C - Conference Paper (international conference)
Pudlák, Pavel - Scheder, D. - Talebanfard, Navid
Tighter Hard Instances for PPSZ.
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 - (Chatzigiannakis, I.; Indyk, P.; Kuhn, F.; Muscholl, A.), s. 1-13, č. článku 85. Leibniz International Proceedings in Informatics, 80. ISBN 978-3-95977-041-5. ISSN 1868-8969.
[44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Warsaw (PL), 10.07.2017-14.07.2017]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : k-SAT * strong exponential time hypothesis * PPSZ * resolution
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7414
Permanent Link: http://hdl.handle.net/11104/0272702File Download Size Commentary Version Access Pudlak2.pdf 2 587.8 KB Publisher’s postprint require - 9.0448832 - MÚ 2016 RIV DE eng C - Conference Paper (international conference)
Galesi, N. - Pudlák, Pavel - Thapen, Neil
The space complexity of cutting planes refutations.
30th Conference on Computational Complexity (CCC 2015). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2015 - (Zuckerman, D.), s. 433-447. Leibniz International Proceedings in Informatics, 33. ISBN 978-3-939897-81-1. ISSN 1868-8969.
[Conference on Computational Complexity (CCC) /30./. Portland (US), 17.06.2015-19.06.2015]
R&D Projects: GA ČR GBP202/12/G061
EU Projects: European Commission(XE) 339691 - FEALORA
Program: FP7
Institutional support: RVO:67985840
Keywords : proof complexity * space * cutting planes
Subject RIV: BA - General Mathematics
http://drops.dagstuhl.de/opus/volltexte/2015/5055/
Permanent Link: http://hdl.handle.net/11104/0250451File Download Size Commentary Version Access Pudlak1.pdf 3 476.6 KB Publisher’s postprint require - 10.0434518 - MÚ 2015 RIV DE eng C - Conference Paper (international conference)
Gavinsky, Dmitry - Pudlák, Pavel
Partition expanders.
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2014 - (Mayr, E.; Portier, N.), s. 325-336. Leibniz International Proceedings in Informatics, 25. ISBN 978-3-939897-65-1. ISSN 1868-8969.
[International Symposium on Theoretical Aspects of Computer Science (STACS 2014), /31./. Lyon (FR), 05.03.2014-08.03.2014]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : partitions * expanders * random graphs
Subject RIV: BA - General Mathematics
http://drops.dagstuhl.de/opus/volltexte/2014/4468/
Permanent Link: http://hdl.handle.net/11104/0238547File Download Size Commentary Version Access Gavinsky3.pdf 1 675.2 KB Publisher’s postprint open-access