Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss Minimization Through the Lens Of Outcome Indistinguishability. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 60:1-60:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{gopalan_et_al:LIPIcs.ITCS.2023.60, author = {Gopalan, Parikshit and Hu, Lunjia and Kim, Michael P. and Reingold, Omer and Wieder, Udi}, title = {{Loss Minimization Through the Lens Of Outcome Indistinguishability}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {60:1--60:20}, 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.60}, URN = {urn:nbn:de:0030-drops-175635}, doi = {10.4230/LIPIcs.ITCS.2023.60}, annote = {Keywords: Loss Minimization, Indistinguishability} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Vladimir Podolskii and Nikolay V. Proskurin. Polynomial Threshold Functions for Decision Lists. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 52:1-52:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{podolskii_et_al:LIPIcs.ISAAC.2022.52, author = {Podolskii, Vladimir and Proskurin, Nikolay V.}, title = {{Polynomial Threshold Functions for Decision Lists}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {52:1--52:12}, 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.52}, URN = {urn:nbn:de:0030-drops-173372}, doi = {10.4230/LIPIcs.ISAAC.2022.52}, annote = {Keywords: Threshold function, decision list, Hamming ball} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Ninad Rajgopal and Rahul Santhanam. On the Structure of Learnability Beyond P/Poly. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 46:1-46:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rajgopal_et_al:LIPIcs.APPROX/RANDOM.2021.46, author = {Rajgopal, Ninad and Santhanam, Rahul}, title = {{On the Structure of Learnability Beyond P/Poly}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {46:1--46:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.46}, URN = {urn:nbn:de:0030-drops-147395}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.46}, annote = {Keywords: Hardness of Learning, Oracle Circuit Classes, Succinct Search, Black-Box Reductions} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goel_et_al:LIPIcs.ITCS.2021.22, author = {Goel, Surbhi and Klivans, Adam and Manurangsi, Pasin and Reichman, Daniel}, title = {{Tight Hardness Results for Training Depth-2 ReLU Networks}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.22}, URN = {urn:nbn:de:0030-drops-135611}, doi = {10.4230/LIPIcs.ITCS.2021.22}, annote = {Keywords: ReLU, Learning Algorithm, Running Time Lower Bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Kuan Cheng and William M. Hoza. Hitting Sets Give Two-Sided Derandomization of Small Space. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 10:1-10:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cheng_et_al:LIPIcs.CCC.2020.10, author = {Cheng, Kuan and Hoza, William M.}, title = {{Hitting Sets Give Two-Sided Derandomization of Small Space}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {10:1--10:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.10}, URN = {urn:nbn:de:0030-drops-125625}, doi = {10.4230/LIPIcs.CCC.2020.10}, annote = {Keywords: hitting sets, derandomization, read-once branching programs} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Guy Blanc, Jane Lange, and Li-Yang Tan. Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 44:1-44:44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{blanc_et_al:LIPIcs.ITCS.2020.44, author = {Blanc, Guy and Lange, Jane and Tan, Li-Yang}, title = {{Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {44:1--44:44}, 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.44}, URN = {urn:nbn:de:0030-drops-117295}, doi = {10.4230/LIPIcs.ITCS.2020.44}, annote = {Keywords: Decision trees, Influence of variables, Analysis of boolean functions, Learning theory, Top-down decision tree heuristics} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, 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.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
William M. Hoza and Adam R. Klivans. Preserving Randomness for Adaptive Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 43:1-43:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{hoza_et_al:LIPIcs.APPROX-RANDOM.2018.43, author = {Hoza, William M. and Klivans, Adam R.}, title = {{Preserving Randomness for Adaptive Algorithms}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {43:1--43:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.43}, URN = {urn:nbn:de:0030-drops-94477}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.43}, annote = {Keywords: pseudorandomness, adaptivity, estimation} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Adam Klivans and Pravesh Kothari. Embedding Hard Learning Problems Into Gaussian Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 793-809, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{klivans_et_al:LIPIcs.APPROX-RANDOM.2014.793, author = {Klivans, Adam and Kothari, Pravesh}, title = {{Embedding Hard Learning Problems Into Gaussian Space}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {793--809}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.793}, URN = {urn:nbn:de:0030-drops-47391}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.793}, annote = {Keywords: distribution-specific hardness of learning, gaussian space, halfspace-learning, agnostic learning} }
Feedback for Dagstuhl Publishing