Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Vinayak M. Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 18:1-18:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kumar:LIPIcs.CCC.2023.18, author = {Kumar, Vinayak M.}, title = {{Tight Correlation Bounds for Circuits Between AC0 and TC0}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {18:1--18:40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.18}, URN = {urn:nbn:de:0030-drops-182885}, doi = {10.4230/LIPIcs.CCC.2023.18}, annote = {Keywords: AC⁰, TC⁰, Switching Lemma, Lower Bounds, Correlation Bounds, Circuit Complexity} }
Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Milan Mossé. Multiplicative Metric Fairness Under Composition. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{mosse:LIPIcs.FORC.2023.4, author = {Moss\'{e}, Milan}, title = {{Multiplicative Metric Fairness Under Composition}}, booktitle = {4th Symposium on Foundations of Responsible Computing (FORC 2023)}, pages = {4:1--4:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-272-3}, ISSN = {1868-8969}, year = {2023}, volume = {256}, editor = {Talwar, Kunal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.4}, URN = {urn:nbn:de:0030-drops-179250}, doi = {10.4230/LIPIcs.FORC.2023.4}, annote = {Keywords: algorithmic fairness, metric fairness, fairness under composition} }
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-dev.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 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)
Milan Mossé, Harry Sha, and Li-Yang Tan. A Generalization of the Satisfiability Coding Lemma and Its Applications. In 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 236, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mosse_et_al:LIPIcs.SAT.2022.9, author = {Moss\'{e}, Milan and Sha, Harry and Tan, Li-Yang}, title = {{A Generalization of the Satisfiability Coding Lemma and Its Applications}}, booktitle = {25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-242-6}, ISSN = {1868-8969}, year = {2022}, volume = {236}, editor = {Meel, Kuldeep S. and Strichman, Ofer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.9}, URN = {urn:nbn:de:0030-drops-166837}, doi = {10.4230/LIPIcs.SAT.2022.9}, annote = {Keywords: Prime Implicants, Satisfiability Coding Lemma, Blake Canonical Form, k-SAT} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The Composition Complexity of Majority. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 19:1-19:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lecomte_et_al:LIPIcs.CCC.2022.19, author = {Lecomte, Victor and Ramakrishnan, Prasanna and Tan, Li-Yang}, title = {{The Composition Complexity of Majority}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {19:1--19:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.19}, URN = {urn:nbn:de:0030-drops-165818}, doi = {10.4230/LIPIcs.CCC.2022.19}, annote = {Keywords: computational complexity, circuit lower bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lyu:LIPIcs.CCC.2022.34, author = {Lyu, Xin}, title = {{Improved Pseudorandom Generators for AC⁰ Circuits}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {34:1--34:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.34}, URN = {urn:nbn:de:0030-drops-165963}, doi = {10.4230/LIPIcs.CCC.2022.34}, annote = {Keywords: pseudorandom generators, derandomization, switching Lemmas, AC⁰} }
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-dev.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: OASIcs, Volume 100, 13th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 11th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2022)
Antonino Tumeo, Nicolas Bohm Agostini, Serena Curzel, Ankur Limaye, Cheng Tan, Vinay Amatya, Marco Minutoli, Vito Giovanni Castellana, Ang Li, and Joseph Manzano. SO(DA)^2: End-to-end Generation of Specialized Reconfigurable Architectures (Invited Talk). In 13th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 11th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2022). Open Access Series in Informatics (OASIcs), Volume 100, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{tumeo_et_al:OASIcs.PARMA-DITAM.2022.1, author = {Tumeo, Antonino and Agostini, Nicolas Bohm and Curzel, Serena and Limaye, Ankur and Tan, Cheng and Amatya, Vinay and Minutoli, Marco and Castellana, Vito Giovanni and Li, Ang and Manzano, Joseph}, title = {{SO(DA)^2: End-to-end Generation of Specialized Reconfigurable Architectures}}, booktitle = {13th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 11th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2022)}, pages = {1:1--1:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-231-0}, ISSN = {2190-6807}, year = {2022}, volume = {100}, editor = {Palumbo, Francesca and Bispo, Jo\~{a}o and Cherubin, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2022.1}, URN = {urn:nbn:de:0030-drops-161175}, doi = {10.4230/OASIcs.PARMA-DITAM.2022.1}, annote = {Keywords: Reconfigurable architectures, data analytics} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Rocco A. Servedio and Li-Yang Tan. Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{servedio_et_al:LIPIcs.APPROX/RANDOM.2021.37, author = {Servedio, Rocco A. and Tan, Li-Yang}, title = {{Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {37:1--37:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.37}, URN = {urn:nbn:de:0030-drops-147304}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.37}, annote = {Keywords: Derandomization, Polynomial threshold functions, deterministic approximate counting} }
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-dev.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 200, 36th Computational Complexity Conference (CCC 2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the Power and Limitations of Branch and Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 6:1-6:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fleming_et_al:LIPIcs.CCC.2021.6, author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Impagliazzo, Russell and Pitassi, Toniann and Robere, Robert and Tan, Li-Yang and Wigderson, Avi}, title = {{On the Power and Limitations of Branch and Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {6:1--6:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.6}, URN = {urn:nbn:de:0030-drops-142809}, doi = {10.4230/LIPIcs.CCC.2021.6}, annote = {Keywords: Proof Complexity, Integer Programming, Cutting Planes, Branch and Cut, Stabbing Planes} }
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-dev.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 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)
Katherine Cordwell, Yong Kiam Tan, and André Platzer. A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cordwell_et_al:LIPIcs.ITP.2021.14, author = {Cordwell, Katherine and Tan, Yong Kiam and Platzer, Andr\'{e}}, title = {{A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm}}, booktitle = {12th International Conference on Interactive Theorem Proving (ITP 2021)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-188-7}, ISSN = {1868-8969}, year = {2021}, volume = {193}, editor = {Cohen, Liron and Kaliszyk, Cezary}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.14}, URN = {urn:nbn:de:0030-drops-139099}, doi = {10.4230/LIPIcs.ITP.2021.14}, annote = {Keywords: quantifier elimination, matrix, theorem proving, real arithmetic} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. The Power of Many Samples in Query Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bassilakis_et_al:LIPIcs.ICALP.2020.9, author = {Bassilakis, Andrew and Drucker, Andrew and G\"{o}\"{o}s, Mika and Hu, Lunjia and Ma, Weiyun and Tan, Li-Yang}, title = {{The Power of Many Samples in Query Complexity}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.9}, URN = {urn:nbn:de:0030-drops-124163}, doi = {10.4230/LIPIcs.ICALP.2020.9}, annote = {Keywords: Query complexity, Composition theorems} }
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-dev.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