Li-Yang Tan

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 106

Top Venues

CoRR

FOCS

Electron. Colloquium Comput. Complex.

STOC

Publications

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
A Strong Direct Sum Theorem for Distributional Query Complexity. CoRR (2024)
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
A Strong Direct Sum Theorem for Distributional Query Complexity. CCC (2024)
Caleb Koch, Carmen Strassle, Li-Yang Tan
The title of the paper. COLT (2024)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Superconstant Inapproximability of Decision Tree Learning. CoRR (2024)
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou
Multitask Learning via Shared Features: Algorithms and Hardness. COLT (2023)
Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, Mo Tiwari
Harnessing the power of choices in decision tree learning. NeurIPS (2023)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Single-Pass Streaming Algorithms for Correlation Clustering. SODA (2023)
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers. CoRR (2023)
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
A strong composition theorem for junta complexity and the boosting of property testers. FOCS (2023)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
Lifting Uniform Learners via Distributional Decomposition. STOC (2023)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Properly Learning Decision Trees with Queries Is NP-Hard. CoRR (2023)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
Lifting uniform learners via distributional decomposition. CoRR (2023)
Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, Mo Tiwari
Harnessing the Power of Choices in Decision Tree Learning. CoRR (2023)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Properly learning decision trees with queries is NP-hard. FOCS (2023)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Superpolynomial lower bounds for decision tree learning and testing. SODA (2023)
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
Certification with an NP Oracle. ITCS (2023)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
Popular decision tree algorithms are provably noise tolerant. CoRR (2022)
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
The Composition Complexity of Majority. CCC (2022)
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou
Multitask Learning via Shared Features: Algorithms and Hardness. CoRR (2022)
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
A query-optimal algorithm for finding counterfactuals. ICML (2022)
Rocco A. Servedio, Li-Yang Tan
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. 18 (2022)
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
A Query-Optimal Algorithm for Finding Counterfactuals. CoRR (2022)
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
The composition complexity of majority. CoRR (2022)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Properly learning decision trees in almost polynomial time. FOCS (2022)
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
Tradeoffs for small-depth Frege proofs. FOCS (2022)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS (2022)
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
The Query Complexity of Certification. CoRR (2022)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
Popular decision tree algorithms are provably noise tolerant. ICML (2022)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
On the power of adaptivity in statistical adversaries. COLT (2022)
Milan Mossé, Harry Sha, Li-Yang Tan
A Generalization of the Satisfiability Coding Lemma and Its Applications. SAT (2022)
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
Certification with an NP Oracle. CoRR (2022)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. J. ACM 69 (2) (2022)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR (2022)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Superpolynomial Lower Bounds for Decision Tree Learning and Testing. CoRR (2022)
Victor Lecomte, Li-Yang Tan
Sharper bounds on the Fourier concentration of DNFs. FOCS (2022)
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
The query complexity of certification. STOC (2022)
Guy Blanc, Jane Lange, Li-Yang Tan
Reconstructing Decision Trees. ICALP (2022)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Properly Learning Decision Trees in almost Polynomial Time. J. ACM 69 (6) (2022)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Open Problem: Properly learning decision trees in polynomial time? CoRR (2022)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Properly learning decision trees in almost polynomial time. CoRR (2021)
Victor Lecomte, Li-Yang Tan
Sharper bounds on the Fourier concentration of DNFs. CoRR (2021)
Guy Blanc, Jane Lange, Li-Yang Tan
Learning Stochastic Decision Trees. ICALP (2021)
Guy Blanc, Jane Lange, Li-Yang Tan
Query strategies for priced information, revisited. SODA (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. CoRR (2021)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. APPROX-RANDOM (2021)
Guy Blanc, Jane Lange, Li-Yang Tan
Provably efficient, succinct, and precise explanations. NeurIPS (2021)
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
Tradeoffs for small-depth Frege proofs. CoRR (2021)
Guy Blanc, Jane Lange, Li-Yang Tan
Learning stochastic decision trees. CoRR (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. 28 (2021)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR (2021)
Rocco A. Servedio, Li-Yang Tan
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Computational Complexity Conference (2021)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Properly learning decision trees in almost polynomial time. FOCS (2021)
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
On the power of adaptivity in statistical adversaries. CoRR (2021)
Guy Blanc, Jane Lange, Li-Yang Tan
Provably efficient, succinct, and precise explanations. CoRR (2021)
Moses Charikar, Weiyun Ma, Li-Yang Tan
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity. PODC (2021)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Decision tree heuristics can fail, even in the smoothed setting. CoRR (2021)
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
Tradeoffs for small-depth Frege proofs. FOCS (2021)
Victor Lecomte, Li-Yang Tan
Sharper bounds on the Fourier concentration of DNFs. FOCS (2021)
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
Universal guarantees for decision tree induction via a higher-order splitting criterion. CoRR (2020)
Guy Blanc, Jane Lange, Li-Yang Tan
Testing and reconstruction via decision trees. CoRR (2020)
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
Non-Malleability against Polynomial Tampering. Electron. Colloquium Comput. Complex. 27 (2020)
Guy Blanc, Jane Lange, Li-Yang Tan
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. ITCS (2020)
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
Non-Malleability against Polynomial Tampering. IACR Cryptol. ePrint Arch. 2020 (2020)
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
Universal guarantees for decision tree induction via a higher-order splitting criterion. NeurIPS (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Guy Blanc, Jane Lange, Li-Yang Tan
Provable guarantees for decision tree induction: the agnostic setting. ICML (2020)
Guy Blanc, Jane Lange, Li-Yang Tan
Provable guarantees for decision tree induction: the agnostic setting. CoRR (2020)
Moses Charikar, Weiyun Ma, Li-Yang Tan
New lower bounds for Massively Parallel Computation from query complexity. CoRR (2020)
Guy Blanc, Jane Lange, Li-Yang Tan
Query strategies for priced information, revisited. CoRR (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. CoRR (2020)
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
Estimating decision tree learnability with polylogarithmic sample complexity. CoRR (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. ICALP (2020)
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
Non-malleability Against Polynomial Tampering. CRYPTO (3) (2020)
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
Estimating decision tree learnability with polylogarithmic sample complexity. NeurIPS (2020)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Gaussian PTFs via local hyperconcentration. STOC (2020)
Moses Charikar, Weiyun Ma, Li-Yang Tan
Unconditional Lower Bounds for Adaptive Massively Parallel Computation. SPAA (2020)
Rocco A. Servedio, Li-Yang Tan
Pseudorandomness for read-k DNF formulas. SODA (2019)
Guy Blanc, Jane Lange, Li-Yang Tan
Top-down induction of decision trees: rigorous guarantees and inherent limitations. CoRR (2019)
Rocco A. Servedio, Li-Yang Tan
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. APPROX-RANDOM (2019)
Guy Blanc, Jane Lange, Li-Yang Tan
Top-down induction of decision trees: rigorous guarantees and inherent limitations. Electron. Colloquium Comput. Complex. 26 (2019)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling polytopes. STOC (2019)
Guy Blanc, Jane Lange, Li-Yang Tan
Constructive derandomization of query algorithms. CoRR (2019)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65 (6) (2018)
Rocco A. Servedio, Li-Yang Tan
Deterministic search for CNF satisfying assignments in almost polynomial time. CoRR (2018)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. Electron. Colloquium Comput. Complex. 25 (2018)
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan
Non-Malleable Codes for Small-Depth Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan
Non-Malleable Codes for Small-Depth Circuits. CoRR (2018)
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan
Non-Malleable Codes for Small-Depth Circuits. IACR Cryptol. ePrint Arch. 2018 (2018)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. CoRR (2018)
Rocco A. Servedio, Li-Yang Tan
Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. CoRR (2018)
Rocco A. Servedio, Li-Yang Tan
Improved pseudorandom generators from pseudorandom multi-switching lemmas. CoRR (2018)
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan
Non-Malleable Codes for Small-Depth Circuits. FOCS (2018)
Rocco A. Servedio, Li-Yang Tan
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. APPROX-RANDOM (2018)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. 24 (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-Adaptive Junta Testing. Computational Complexity Conference (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR (2017)
Rocco A. Servedio, Li-Yang Tan
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. FOCS (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM (2017)

Li-Yang Tan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Li-Yang Tan