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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lisa Hellerstein, Naifeng Liu, and Kevin Schewior. Quickly Determining Who Won an Election. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hellerstein_et_al:LIPIcs.ITCS.2024.61, author = {Hellerstein, Lisa and Liu, Naifeng and Schewior, Kevin}, title = {{Quickly Determining Who Won an Election}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {61:1--61:14}, 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.61}, URN = {urn:nbn:de:0030-drops-195890}, doi = {10.4230/LIPIcs.ITCS.2024.61}, annote = {Keywords: stochastic function evaluation, voting, approximation algorithms} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3, author = {Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal}, title = {{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {3:1--3:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3}, URN = {urn:nbn:de:0030-drops-172880}, doi = {10.4230/LIPIcs.ISAAC.2022.3}, annote = {Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik. The Stochastic Score Classification Problem. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gkenosis_et_al:LIPIcs.ESA.2018.36, author = {Gkenosis, Dimitrios and Grammel, Nathaniel and Hellerstein, Lisa and Kletenik, Devorah}, title = {{The Stochastic Score Classification Problem}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.36}, URN = {urn:nbn:de:0030-drops-94990}, doi = {10.4230/LIPIcs.ESA.2018.36}, annote = {Keywords: approximation algorithms, symmetric Boolean functions, stochastic probing, sequential testing, adaptivity} }