Guy Blanc
Contact: gblanc (at) stanford.edu
 |
I'm Guy, a PhD student in the Stanford CS theory group. I am extremely fortunate to be advised by Li-Yang Tan. My research is generously supported by a Jane Street Graduate Research Fellowship. In my free time, I enjoy hiking, dancing, and playing/watching sports. |
Selected publications
- Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc and Gregory Valiant
STOC 2025
Invited to STOC 2025 special issue
- The sample complexity of smooth boosting and the tightness of the hardcore theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch, and Li-Yang Tan
FOCS 2024
Invited to FOCS 2024 special issue
- Subsampling Suffices for Adaptive Data Analysis
Guy Blanc
STOC 2023
Best student paper at STOC 2023
Invited to STOC 2023 special issue
Journal of the ACM, 2025
- Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan
FOCS 2021
Invited to FOCS 2021 special issue
Journal of the ACM, 2022
All publications
In my field, we generally order authors alphabetically by last name.
- Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, and Rocco Servedio
SODA 2026, to appear
- Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan
FOCS 2025, to appear
- Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément Canonne, and Erik Waingarten
FOCS 2025, to appear
- Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc and Gregory Valiant
STOC 2025
Invited to STOC 2025 special issue
- A Distributional-Lifting Theorem for PAC Learning
Guy Blanc, Jane Lange, Carmen Strassle, and Li-Yang Tan
COLT 2025
- The sample complexity of smooth boosting and the tightness of the hardcore theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch, and Li-Yang Tan
FOCS 2024
Invited to FOCS 2024 special issue
- A strong direct sum theorem for distributional query complexity
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan
CCC 2024
Invited to CCC 2024 special issue
- A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan
FOCS 2023
- Harnessing the Power of Choices in Decision Tree Learning
Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, and Mo Tiwari
NeurIPS 2023
- Subsampling Suffices for Adaptive Data Analysis
Guy Blanc
STOC 2023
Best student paper at STOC 2023
Invited to STOC 2023 special issue
Journal of the ACM, 2025
- Lifting uniform learners via distributional decomposition
Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan
STOC 2023
- Multitask Learning via Shared Features: Algorithms and Hardness
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou
COLT 2023
- Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan
ITCS 2023
- A query-optimal algorithm for finding counterfactuals
Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan
ICML 2022
- Popular decision tree algorithms are provably noise tolerant
Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan
ICML 2022
- On the power of adaptivity in statistical adversaries
Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan
COLT 2022
- Open problem: Properly learning decision trees in polynomial time?
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan
COLT 2022
Open problems track
- New Near-Linear Time Decodable Codes Closer to the GV Bound
Guy Blanc and Dean Doron
CCC 2022
- Reconstructing decision trees
Guy Blanc, Jane Lange, and Li-Yang Tan
ICALP 2022
- The query complexity of certification
Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan
STOC 2022
- Provably efficient, succinct, and precise explanations
Guy Blanc, Jane Lange, and Li-Yang Tan
NeurIPS 2021
- Multiway online correlated selection
Guy Blanc and Moses Charikar
FOCS 2021
- Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan
FOCS 2021
Invited to FOCS 2021 special issue
Journal of the ACM, 2022
- Decision tree heuristics can fail, even in the smoothed setting
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan
RANDOM 2021
- Learning stochastic decision trees
Guy Blanc, Jane Lange, and Li-Yang Tan
ICALP 2021
- Query strategies for priced information, revisited
Guy Blanc, Jane Lange, and Li-Yang Tan
SODA 2021
- Universal guarantees for decision tree induction via a higher-order splitting criterion
Guy Blanc, Neha Gupta, Jane Lange, and Li-Yang Tan
NeurIPS 2020
- Estimating decision tree learnability with polylogarithmic sample complexity
Guy Blanc, Neha Gupta, Jane Lange, and Li-Yang Tan
NeurIPS 2020
- Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant
COLT 2020
- Provable guarantees for decision tree induction: the agnostic setting
Guy Blanc, Jane Lange, and Li-Yang Tan
ICML 2020
- Top-down induction of decision trees: rigorous guarantees and inherent limitations
Guy Blanc, Jane Lange, and Li-Yang Tan
ITCS 2020
- Adaptive sampled softmax with kernel based sampling
Guy Blanc, Steffen Rendle
ICML 2018