Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
Jane Lange and Mingda Qiao. Limitations of Membership Queries in Testable Learning. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 91:1-91:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{lange_et_al:LIPIcs.ITCS.2026.91,
author = {Lange, Jane and Qiao, Mingda},
title = {{Limitations of Membership Queries in Testable Learning}},
booktitle = {17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
pages = {91:1--91:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-410-9},
ISSN = {1868-8969},
year = {2026},
volume = {362},
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.ITCS.2026.91},
URN = {urn:nbn:de:0030-drops-253785},
doi = {10.4230/LIPIcs.ITCS.2026.91},
annote = {Keywords: Testable learning, PAC learning}
}
Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Omri Ben-Eliezer, Tomer Grossman, and Moni Naor. On the Instance Optimality of Detecting Collisions and Subgraphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2025.23,
author = {Ben-Eliezer, Omri and Grossman, Tomer and Naor, Moni},
title = {{On the Instance Optimality of Detecting Collisions and Subgraphs}},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
pages = {23:1--23:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-372-0},
ISSN = {1868-8969},
year = {2025},
volume = {334},
editor = {Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.23},
URN = {urn:nbn:de:0030-drops-234002},
doi = {10.4230/LIPIcs.ICALP.2025.23},
annote = {Keywords: instance optimality, instance complexity, unlabeled certificate, subgraph detection, collision detection}
}
Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)
Jason Hartline, Yifan Wu, and Yunran Yang. Smooth Calibration and Decision Making. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{hartline_et_al:LIPIcs.FORC.2025.16,
author = {Hartline, Jason and Wu, Yifan and Yang, Yunran},
title = {{Smooth Calibration and Decision Making}},
booktitle = {6th Symposium on Foundations of Responsible Computing (FORC 2025)},
pages = {16:1--16:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-367-6},
ISSN = {1868-8969},
year = {2025},
volume = {329},
editor = {Bun, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.16},
URN = {urn:nbn:de:0030-drops-231438},
doi = {10.4230/LIPIcs.FORC.2025.16},
annote = {Keywords: Calibration, calibration errors, decision making, differential privacy}
}
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Aadityan Ganesh and Jason Hartline. Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{ganesh_et_al:LIPIcs.ITCS.2025.52,
author = {Ganesh, Aadityan and Hartline, Jason},
title = {{Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions)}},
booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
pages = {52:1--52:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-361-4},
ISSN = {1868-8969},
year = {2025},
volume = {325},
editor = {Meka, Raghu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.52},
URN = {urn:nbn:de:0030-drops-226808},
doi = {10.4230/LIPIcs.ITCS.2025.52},
annote = {Keywords: Pen testing, consumer surplus, money-burning, deferred-acceptance auctions}
}
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Weihao Kong, Mingda Qiao, and Rajat Sen. A Combinatorial Approach to Robust PCA. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 70:1-70:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kong_et_al:LIPIcs.ITCS.2024.70,
author = {Kong, Weihao and Qiao, Mingda and Sen, Rajat},
title = {{A Combinatorial Approach to Robust PCA}},
booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
pages = {70:1--70:22},
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.70},
URN = {urn:nbn:de:0030-drops-195984},
doi = {10.4230/LIPIcs.ITCS.2024.70},
annote = {Keywords: Robust PCA, Sparse Recovery, Robust Statistics}
}
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 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 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}
}