Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan. Certification with an NP Oracle. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 18:1-18:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{blanc_et_al:LIPIcs.ITCS.2023.18, author = {Blanc, Guy and Koch, Caleb and Lange, Jane and Strassle, Carmen and Tan, Li-Yang}, title = {{Certification with an NP Oracle}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {18:1--18:22}, 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.18}, URN = {urn:nbn:de:0030-drops-175217}, doi = {10.4230/LIPIcs.ITCS.2023.18}, annote = {Keywords: Certificate complexity, Boolean functions, polynomial hierarchy, hardness of approximation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Guy Blanc, Jane Lange, and Li-Yang Tan. Reconstructing Decision Trees. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 24:1-24:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{blanc_et_al:LIPIcs.ICALP.2022.24, author = {Blanc, Guy and Lange, Jane and Tan, Li-Yang}, title = {{Reconstructing Decision Trees}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {24:1--24:17}, 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.24}, URN = {urn:nbn:de:0030-drops-163653}, doi = {10.4230/LIPIcs.ICALP.2022.24}, annote = {Keywords: Property reconstruction, property testing, tolerant testing, decision trees} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38, author = {Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten}, title = {{On Comparable Box Dimension}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38}, URN = {urn:nbn:de:0030-drops-160461}, doi = {10.4230/LIPIcs.SoCG.2022.38}, annote = {Keywords: geometric graphs, minor-closed graph classes, treewidth fragility} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan. Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 45:1-45:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blanc_et_al:LIPIcs.APPROX/RANDOM.2021.45, author = {Blanc, Guy and Lange, Jane and Qiao, Mingda and Tan, Li-Yang}, title = {{Decision Tree Heuristics Can Fail, Even in the Smoothed Setting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {45:1--45:16}, 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.45}, URN = {urn:nbn:de:0030-drops-147386}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.45}, annote = {Keywords: decision trees, learning theory, smoothed analysis} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Guy Blanc, Jane Lange, and Li-Yang Tan. Learning Stochastic Decision Trees. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 30:1-30:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blanc_et_al:LIPIcs.ICALP.2021.30, author = {Blanc, Guy and Lange, Jane and Tan, Li-Yang}, title = {{Learning Stochastic Decision Trees}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {30:1--30:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.30}, URN = {urn:nbn:de:0030-drops-140994}, doi = {10.4230/LIPIcs.ICALP.2021.30}, annote = {Keywords: Learning theory, decision trees, proper learning algorithms, adversarial noise} }
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} }
Feedback for Dagstuhl Publishing