Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Wout Vanroose, Ignace Bleukx, Jo Devriendt, Dimos Tsouros, Hélène Verhaeghe, and Tias Guns. Mutational Fuzz Testing for Constraint Modeling Systems. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 29:1-29:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{vanroose_et_al:LIPIcs.CP.2024.29, author = {Vanroose, Wout and Bleukx, Ignace and Devriendt, Jo and Tsouros, Dimos and Verhaeghe, H\'{e}l\`{e}ne and Guns, Tias}, title = {{Mutational Fuzz Testing for Constraint Modeling Systems}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {29:1--29:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.29}, URN = {urn:nbn:de:0030-drops-207149}, doi = {10.4230/LIPIcs.CP.2024.29}, annote = {Keywords: fuzz testing, Constraint modeling language, bugs, mutational testing, modeling, constraint reformulation} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael Saks, and Navid Talebanfard. Local Enumeration and Majority Lower Bounds. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gurumukhani_et_al:LIPIcs.CCC.2024.17, author = {Gurumukhani, Mohit and Paturi, Ramamohan and Pudl\'{a}k, Pavel and Saks, Michael and Talebanfard, Navid}, title = {{Local Enumeration and Majority Lower Bounds}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {17:1--17:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.17}, URN = {urn:nbn:de:0030-drops-204136}, doi = {10.4230/LIPIcs.CCC.2024.17}, annote = {Keywords: Depth 3 circuits, k-CNF satisfiability, Circuit lower bounds, Majority function} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Elie Abboud and Noga Ron-Zewi. Finer-Grained Reductions in Fine-Grained Hardness of Approximation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2024.7, author = {Abboud, Elie and Ron-Zewi, Noga}, title = {{Finer-Grained Reductions in Fine-Grained Hardness of Approximation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.7}, URN = {urn:nbn:de:0030-drops-201507}, doi = {10.4230/LIPIcs.ICALP.2024.7}, annote = {Keywords: Fine-grained complexity, conditional lower bound, fine-grained reduction, Approximation algorithms, Analysis of algorithms, Computational geometry, Computational and structural complexity theory} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)
Marc Vinyals, Chunxiao Li, Noah Fleming, Antonina Kolokolova, and Vijay Ganesh. Limits of CDCL Learning via Merge Resolution. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vinyals_et_al:LIPIcs.SAT.2023.27, author = {Vinyals, Marc and Li, Chunxiao and Fleming, Noah and Kolokolova, Antonina and Ganesh, Vijay}, title = {{Limits of CDCL Learning via Merge Resolution}}, booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)}, pages = {27:1--27:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-286-0}, ISSN = {1868-8969}, year = {2023}, volume = {271}, editor = {Mahajan, Meena and Slivovsky, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.27}, URN = {urn:nbn:de:0030-drops-184894}, doi = {10.4230/LIPIcs.SAT.2023.27}, annote = {Keywords: proof complexity, resolution, merge resolution, CDCL, learning scheme} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Lifting for Constant-Depth Circuits and Applications to MCSP. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{carmosino_et_al:LIPIcs.ICALP.2021.44, author = {Carmosino, Marco and Hoover, Kenneth and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Lifting for Constant-Depth Circuits and Applications to MCSP}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {44:1--44:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.44}, URN = {urn:nbn:de:0030-drops-141135}, doi = {10.4230/LIPIcs.ICALP.2021.44}, annote = {Keywords: circuit complexity, constant-depth circuits, lifting theorems, Minimum Circuit Size Problem, reductions, Switching Lemma} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC^0[p] Lower Bounds Against MCSP via the Coin Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.ICALP.2019.66, author = {Golovnev, Alexander and Ilango, Rahul and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and Tal, Avishay}, title = {{AC^0\lbrackp\rbrack Lower Bounds Against MCSP via the Coin Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {66:1--66:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.66}, URN = {urn:nbn:de:0030-drops-106422}, doi = {10.4230/LIPIcs.ICALP.2019.66}, annote = {Keywords: Minimum Circuit Size Problem (MCSP), circuit lower bounds, AC0\lbrackp\rbrack, coin problem, hybrid argument, MKTP, biased random boolean functions} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, and Robert Robere. Stabbing Planes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{beame_et_al:LIPIcs.ITCS.2018.10, author = {Beame, Paul and Fleming, Noah and Impagliazzo, Russell and Kolokolova, Antonina and Pankratov, Denis and Pitassi, Toniann and Robere, Robert}, title = {{Stabbing Planes}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.10}, URN = {urn:nbn:de:0030-drops-83418}, doi = {10.4230/LIPIcs.ITCS.2018.10}, annote = {Keywords: Complexity Theory, Proof Complexity, Communication Complexity, Cutting Planes, Semi-Algebraic Proof Systems, Pseudo Boolean Solvers, SAT solvers, Inte} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does Looking Inside a Circuit Help?. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{impagliazzo_et_al:LIPIcs.MFCS.2017.1, author = {Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and McKenzie, Pierre and Romani, Shadab}, title = {{Does Looking Inside a Circuit Help?}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.1}, URN = {urn:nbn:de:0030-drops-80975}, doi = {10.4230/LIPIcs.MFCS.2017.1}, annote = {Keywords: Black-Box Hypothesis, Rice's theorem, circuit complexity, SAT, sensitivity of boolean functions, decision tree complexity} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, and Michal Koucky. Expander Construction in VNC1. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 31:1-31:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{buss_et_al:LIPIcs.ITCS.2017.31, author = {Buss, Sam and Kabanets, Valentine and Kolokolova, Antonina and Koucky, Michal}, title = {{Expander Construction in VNC1}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {31:1--31:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.31}, URN = {urn:nbn:de:0030-drops-81871}, doi = {10.4230/LIPIcs.ITCS.2017.31}, annote = {Keywords: expander graphs, bounded arithmetic, alternating log time, sequent calculus, monotone propositional logic} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic Learning from Tolerant Natural Proofs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2017.35, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Agnostic Learning from Tolerant Natural Proofs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {35:1--35:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.35}, URN = {urn:nbn:de:0030-drops-75842}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.35}, annote = {Keywords: agnostic learning, natural proofs, circuit lower bounds, meta-algorithms, AC0\lbrackq\rbrack, Nisan-Wigderson generator} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{carmosino_et_al:LIPIcs.CCC.2016.10, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Learning Algorithms from Natural Proofs}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {10:1--10:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.10}, URN = {urn:nbn:de:0030-drops-58557}, doi = {10.4230/LIPIcs.CCC.2016.10}, annote = {Keywords: natural proofs, circuit complexity, lower bounds, learning, compression} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 645-658, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2015.645, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Tighter Connections between Derandomization and Circuit Lower Bounds}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {645--658}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.645}, URN = {urn:nbn:de:0030-drops-53285}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.645}, annote = {Keywords: derandomization, circuit lower bounds, polynomial identity testing, promise BPP, hardness vs. randomness} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An Axiomatic Approach to Algebrization. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{impagliazzo_et_al:DagSemProc.09421.3, author = {Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{An Axiomatic Approach to Algebrization}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.3}, URN = {urn:nbn:de:0030-drops-24150}, doi = {10.4230/DagSemProc.09421.3}, annote = {Keywords: Oracles, arithmetization, algebrization} }