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)
Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 94:1-94:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jin_et_al:LIPIcs.ICALP.2024.94, author = {Jin, Ce and Wu, Hongxun}, title = {{A Faster Algorithm for Pigeonhole Equal Sums}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {94:1--94:11}, 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.94}, URN = {urn:nbn:de:0030-drops-202375}, doi = {10.4230/LIPIcs.ICALP.2024.94}, annote = {Keywords: Subset Sum, Pigeonhole, PPP} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen:LIPIcs.ITCS.2023.34, author = {Chen, Lijie}, title = {{New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.34}, URN = {urn:nbn:de:0030-drops-175373}, doi = {10.4230/LIPIcs.ITCS.2023.34}, annote = {Keywords: Circuit Lower Bounds, Derandomization, Algorithmic Method, ACC} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Nikhil Vyas and Ryan Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 99:1-99:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vyas_et_al:LIPIcs.ITCS.2023.99, author = {Vyas, Nikhil and Williams, Ryan}, title = {{On Oracles and Algorithmic Methods for Proving Lower Bounds}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {99:1--99:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.99}, URN = {urn:nbn:de:0030-drops-176021}, doi = {10.4230/LIPIcs.ITCS.2023.99}, annote = {Keywords: oracles, relativization, circuit complexity, missing string, exponential hierarchy} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, and Ryan Williams. On the Number of Quantifiers as a Complexity Measure. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fagin_et_al:LIPIcs.MFCS.2022.48, author = {Fagin, Ronald and Lenchner, Jonathan and Vyas, Nikhil and Williams, Ryan}, title = {{On the Number of Quantifiers as a Complexity Measure}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.48}, URN = {urn:nbn:de:0030-drops-168460}, doi = {10.4230/LIPIcs.MFCS.2022.48}, annote = {Keywords: number of quantifiers, multi-structural games, complexity measure, s-t connectivity, trees, rooted trees} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Mitali Bafna and Nikhil Vyas. Optimal Fine-Grained Hardness of Approximation of Linear Equations. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bafna_et_al:LIPIcs.ICALP.2021.20, author = {Bafna, Mitali and Vyas, Nikhil}, title = {{Optimal Fine-Grained Hardness of Approximation of Linear Equations}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {20:1--20:19}, 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.20}, URN = {urn:nbn:de:0030-drops-140894}, doi = {10.4230/LIPIcs.ICALP.2021.20}, annote = {Keywords: Linear Equations, Fine-Grained Complexity, Hardness of Approximation} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andrea Lincoln and Adam Yedidia. Faster Random k-CNF Satisfiability. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 78:1-78:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lincoln_et_al:LIPIcs.ICALP.2020.78, author = {Lincoln, Andrea and Yedidia, Adam}, title = {{Faster Random k-CNF Satisfiability}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {78:1--78:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.78}, URN = {urn:nbn:de:0030-drops-124857}, doi = {10.4230/LIPIcs.ICALP.2020.78}, annote = {Keywords: Random k-SAT, Average-Case, Algorithms} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{akshay_et_al:LIPIcs.STACS.2020.37, author = {Akshay, S. and Balaji, Nikhil and Murhekar, Aniket and Varma, Rohith and Vyas, Nikhil}, title = {{Near-Optimal Complexity Bounds for Fragments of the Skolem Problem}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.37}, URN = {urn:nbn:de:0030-drops-118982}, doi = {10.4230/LIPIcs.STACS.2020.37}, annote = {Keywords: Linear Recurrences, Skolem problem, NP-completeness, Weighted automata} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Nikhil Vyas and R. Ryan Williams. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{vyas_et_al:LIPIcs.STACS.2020.59, author = {Vyas, Nikhil and Williams, R. Ryan}, title = {{Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {59:1--59:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.59}, URN = {urn:nbn:de:0030-drops-119200}, doi = {10.4230/LIPIcs.STACS.2020.59}, annote = {Keywords: #SAT, satisfiability, circuit complexity, exact majority, ACC} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Andrea Lincoln and Nikhil Vyas. Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lincoln_et_al:LIPIcs.ITCS.2020.11, author = {Lincoln, Andrea and Vyas, Nikhil}, title = {{Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.11}, URN = {urn:nbn:de:0030-drops-116969}, doi = {10.4230/LIPIcs.ITCS.2020.11}, annote = {Keywords: k-cycle, Space, Savitch, Sparse Graphs, Max-3-SAT} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Mitali Bafna and Nikhil Vyas. Imperfect Gaps in Gap-ETH and PCPs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bafna_et_al:LIPIcs.CCC.2019.32, author = {Bafna, Mitali and Vyas, Nikhil}, title = {{Imperfect Gaps in Gap-ETH and PCPs}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {32:1--32:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.32}, URN = {urn:nbn:de:0030-drops-108545}, doi = {10.4230/LIPIcs.CCC.2019.32}, annote = {Keywords: PCP, Gap-ETH, Hardness of Approximation} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.46, author = {Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole and Xu, Yinzhan and Yu, Yuancheng}, title = {{Approximation Algorithms for Min-Distance Problems}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {46:1--46:14}, 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.46}, URN = {urn:nbn:de:0030-drops-106223}, doi = {10.4230/LIPIcs.ICALP.2019.46}, annote = {Keywords: fine-grained complexity, graph algorithms, diameter, radius, eccentricities} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.47, author = {Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole}, title = {{Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {47:1--47: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.47}, URN = {urn:nbn:de:0030-drops-106238}, doi = {10.4230/LIPIcs.ICALP.2019.47}, annote = {Keywords: approximation algorithms, fine-grained complexity, diameter, radius, eccentricities} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Akshay S., Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{s._et_al:LIPIcs.MFCS.2017.78, author = {S., Akshay and Balaji, Nikhil and Vyas, Nikhil}, title = {{Complexity of Restricted Variants of Skolem and Related Problems}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {78:1--78:14}, 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.78}, URN = {urn:nbn:de:0030-drops-81306}, doi = {10.4230/LIPIcs.MFCS.2017.78}, annote = {Keywords: Linear recurrence sequences, Skolem problem, NP-completeness, Program termination} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas. On Regularity of Unary Probabilistic Automata. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{akshay_et_al:LIPIcs.STACS.2016.8, author = {Akshay, S. and Genest, Blaise and Karelovic, Bruno and Vyas, Nikhil}, title = {{On Regularity of Unary Probabilistic Automata}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.8}, URN = {urn:nbn:de:0030-drops-57093}, doi = {10.4230/LIPIcs.STACS.2016.8}, annote = {Keywords: Probabilistic automata, Symbolic dynamics, Markov chains, Skolem problem, Regularity} }