Guy Blanc
Contact: gblanc (at) mit.edu
 Photo credit to my wonderful fiancée, Sam. Image taken at Glacier National Park |
I'm Guy, a Norbert Wiener Postdoctoral Fellow at MIT mentored by Ankur Moitra. Before that, I completed my PhD in the Stanford CS theory group where I was extremely fortunate to be advised by Li-Yang Tan. My research is in theoretical computer science, with an emphasis on learning theory. I'm especially interested in developing theoretical frameworks that accurately capture properties that make learning algorithms effective in practice, such as robustness, privacy, and generalization. More generally, I'm drawn to broad and conceptual questions that are motivated by modern computational challenges. For example, my recent work adds to our understanding of the nature of problems that admit exponential quantum speedups. My work has been recognized with a best paper award at SODA 2026, a best student paper award at STOC 2023, special issue invitations at STOC 2025, FOCS 2024, CCC 2024, and FOCS 2021, and a Jane Street Graduate Research Fellowship. |
Selected publications
- Robust Learning with Optimal Error
Guy Blanc
FOCS 2026, to appear
See also an excellent followup by Adam Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, and Arsen Vasilyan
- Quantum Speedups Require Structure or Depth
Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan
FOCS 2026, to appear
See also our blog post
- Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, and Rocco Servedio
SODA 2026, best paper award
- Differential privacy from axioms
Guy Blanc, William Pires, and Toniann Pitassi
ITCS 2026
- Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc and Gregory Valiant
STOC 2025
Invited to STOC 2025 special issue
- Subsampling Suffices for Adaptive Data Analysis
Guy Blanc
STOC 2023, best student paper award
Invited to STOC 2023 special issue
Journal of the ACM, 2025
All publications
In my field, we typically order authors alphabetically by last name.
- Robust Learning with Optimal Error
Guy Blanc
FOCS 2026, to appear
See also an excellent followup by Adam Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, and Arsen Vasilyan
- Quantum Speedups Require Structure or Depth
Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan
FOCS 2026, to appear
See also our blog post
- The power of quantum circuits in sampling
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan
TQC 2026, to appear
- Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, and Rocco Servedio
SODA 2026, best paper award
- Differential privacy from axioms
Guy Blanc, William Pires, and Toniann Pitassi
ITCS 2026
- Samplability makes learning easier
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan
ITCS 2026
- Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan
FOCS 2025
- Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément Canonne, and Erik Waingarten
FOCS 2025
- 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
Journal of the ACM, to appear
- 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 studennt paper award
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