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-dev.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 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2, author = {Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum}, title = {{Tracking the l\underline2 Norm with Constant Update Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {2:1--2:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.2}, URN = {urn:nbn:de:0030-drops-112175}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2}, annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch} }
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-dev.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 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bafna_et_al:LIPIcs.MFCS.2016.16, author = {Bafna, Mitali and Lokam, Satyanarayana V. and Tavenas, S\'{e}bastien and Velingker, Ameya}, title = {{On the Sensitivity Conjecture for Read-k Formulas}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16}, URN = {urn:nbn:de:0030-drops-64317}, doi = {10.4230/LIPIcs.MFCS.2016.16}, annote = {Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions} }
Feedback for Dagstuhl Publishing