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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 62:1-62:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{henzinger_et_al:LIPIcs.ITCS.2024.62, author = {Henzinger, Monika and Saha, Barna and Seybold, Martin P. and Ye, Christopher}, title = {{On the Complexity of Algorithms with Predictions for Dynamic Graph Problems}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {62:1--62:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.62}, URN = {urn:nbn:de:0030-drops-195907}, doi = {10.4230/LIPIcs.ITCS.2024.62}, annote = {Keywords: Dynamic Graph Algorithms, Algorithms with Predictions} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Justin Holmgren, Andrea Lincoln, and Ron D. Rothblum. Delegation for Search Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 73:1-73:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{holmgren_et_al:LIPIcs.ICALP.2022.73, author = {Holmgren, Justin and Lincoln, Andrea and Rothblum, Ron D.}, title = {{Delegation for Search Problems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {73:1--73:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.73}, URN = {urn:nbn:de:0030-drops-164146}, doi = {10.4230/LIPIcs.ICALP.2022.73}, annote = {Keywords: Interactive Proofs, Fine-Grained Complexity, Delegation} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Rathish Das, Andrea Lincoln, Jayson Lynch, and J. Ian Munro. Dynamic Boolean Formula Evaluation. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{das_et_al:LIPIcs.ISAAC.2021.61, author = {Das, Rathish and Lincoln, Andrea and Lynch, Jayson and Munro, J. Ian}, title = {{Dynamic Boolean Formula Evaluation}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {61:1--61:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.61}, URN = {urn:nbn:de:0030-drops-154945}, doi = {10.4230/LIPIcs.ISAAC.2021.61}, annote = {Keywords: Data Structures, SAT, Dynamic Algorithms, Boolean Formulas, Fine-grained Complexity, Parallel Algorithms} }
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 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 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lincoln_et_al:LIPIcs.ITCS.2020.53, author = {Lincoln, Andrea and Polak, Adam and Vassilevska Williams, Virginia}, title = {{Monochromatic Triangles, Intermediate Matrix Products, and Convolutions}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {53:1--53:18}, 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.53}, URN = {urn:nbn:de:0030-drops-117382}, doi = {10.4230/LIPIcs.ITCS.2020.53}, annote = {Keywords: 3SUM, fine-grained complexity, matrix multiplication, monochromatic triangle} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.ITCS.2018.34, author = {Demaine, Erik D. and Lincoln, Andrea and Liu, Quanquan C. and Lynch, Jayson and Vassilevska Williams, Virginia}, title = {{Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {34:1--34:23}, 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.34}, URN = {urn:nbn:de:0030-drops-83335}, doi = {10.4230/LIPIcs.ITCS.2018.34}, annote = {Keywords: IO model, Fine-grained Complexity, Algorithms} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 26:1-26:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{henzinger_et_al:LIPIcs.ITCS.2017.26, author = {Henzinger, Monika and Lincoln, Andrea and Neumann, Stefan and Vassilevska Williams, Virginia}, title = {{Conditional Hardness for Sensitivity Problems}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {26:1--26:31}, 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.26}, URN = {urn:nbn:de:0030-drops-81783}, doi = {10.4230/LIPIcs.ITCS.2017.26}, annote = {Keywords: sensitivity, conditional lower bounds, data structures, dynamic graph algorithms} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Trade-Offs for k-SUM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{lincoln_et_al:LIPIcs.ICALP.2016.58, author = {Lincoln, Andrea and Vassilevska Williams, Virginia and Wang, Joshua R. and Williams, R. Ryan}, title = {{Deterministic Time-Space Trade-Offs for k-SUM}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {58:1--58:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.58}, URN = {urn:nbn:de:0030-drops-62250}, doi = {10.4230/LIPIcs.ICALP.2016.58}, annote = {Keywords: 3SUM, kSUM, time-space tradeoff, algorithm} }