Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Gregory Valiant. Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 96:1-96:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{valiant:LIPIcs.ITCS.2024.96, author = {Valiant, Gregory}, title = {{Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {96:1--96:13}, 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.96}, URN = {urn:nbn:de:0030-drops-196248}, doi = {10.4230/LIPIcs.ITCS.2024.96}, annote = {Keywords: Physics based computing, matrix multiplication, low-energy computing} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Mingda Qiao and Gregory Valiant. Online Pen Testing. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 91:1-91:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{qiao_et_al:LIPIcs.ITCS.2023.91, author = {Qiao, Mingda and Valiant, Gregory}, title = {{Online Pen Testing}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {91:1--91: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.91}, URN = {urn:nbn:de:0030-drops-175940}, doi = {10.4230/LIPIcs.ITCS.2023.91}, annote = {Keywords: Optimal stopping, online algorithm} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{steinhardt_et_al:LIPIcs.ITCS.2018.45, author = {Steinhardt, Jacob and Charikar, Moses and Valiant, Gregory}, title = {{Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {45:1--45:21}, 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.45}, URN = {urn:nbn:de:0030-drops-83687}, doi = {10.4230/LIPIcs.ITCS.2018.45}, annote = {Keywords: robust learning, outliers, stochastic block models, p-norm estimation} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Qingqing Huang, Sham M. Kakade, Weihao Kong, and Gregory Valiant. Recovering Structured Probability Matrices. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{huang_et_al:LIPIcs.ITCS.2018.46, author = {Huang, Qingqing and Kakade, Sham M. and Kong, Weihao and Valiant, Gregory}, title = {{Recovering Structured Probability Matrices}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {46:1--46:14}, 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.46}, URN = {urn:nbn:de:0030-drops-83625}, doi = {10.4230/LIPIcs.ITCS.2018.46}, annote = {Keywords: Random matrices, matrix recovery, stochastic block model, Hidden Markov Models} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Mingda Qiao and Gregory Valiant. Learning Discrete Distributions from Untrusted Batches. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{qiao_et_al:LIPIcs.ITCS.2018.47, author = {Qiao, Mingda and Valiant, Gregory}, title = {{Learning Discrete Distributions from Untrusted Batches}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {47:1--47: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.47}, URN = {urn:nbn:de:0030-drops-83215}, doi = {10.4230/LIPIcs.ITCS.2018.47}, annote = {Keywords: robust statistics, information-theoretic optimality} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Michael Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. Stochastic Streams: Sample Complexity vs. Space Complexity. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{crouch_et_al:LIPIcs.ESA.2016.32, author = {Crouch, Michael and McGregor, Andrew and Valiant, Gregory and Woodruff, David P.}, title = {{Stochastic Streams: Sample Complexity vs. Space Complexity}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {32:1--32:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.32}, URN = {urn:nbn:de:0030-drops-63838}, doi = {10.4230/LIPIcs.ESA.2016.32}, annote = {Keywords: data streams, sample complexity, frequency moments, graph connectivity, subspace approximation} }
Feedback for Dagstuhl Publishing