default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDLi-Yang Tan
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2014
[b1]Li-Yang Tan:
Analytic Methods in Concrete Complexity. Columbia University, USA, 2014
Journal Articles
- 2022
- [j12]Ryan O'Donnell, Rocco A. Servedio
, Li-Yang Tan:
Fooling Polytopes. J. ACM 69(2): 9:1-9:37 (2022) - [j11]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Properly Learning Decision Trees in almost Polynomial Time. J. ACM 69(6): 39:1-39:19 (2022) - [j10]Rocco A. Servedio, Li-Yang Tan:
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. 18: 1-46 (2022) - 2018
- [j9]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): 40:1-40:18 (2018) - 2017
- [j8]Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64(5): 35:1-35:27 (2017) - 2015
- [j7]Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
Noise Stable Halfspaces are Close to Very Small Juntas. Chic. J. Theor. Comput. Sci. 2015 (2015) - [j6]Eric Blais, Li-Yang Tan:
Approximating Boolean Functions with Depth-2 Circuits. SIAM J. Comput. 44(6): 1583-1600 (2015) - [j5]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. SIGACT News 46(4): 50-68 (2015) - 2014
- [j4]Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. SIAM J. Comput. 43(1): 231-253 (2014) - [j3]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions. Theory Comput. 10: 27-53 (2014) - [j2]Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright:
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. ACM Trans. Comput. Theory 6(1): 2:1-2:20 (2014) - 2013
- [j1]Eric Blais, Li-Yang Tan:
Hypercontractivity Via the Entropy Method. Theory Comput. 9: 889-896 (2013)
Conference and Workshop Papers
- 2024
- [c66]Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A Strong Direct Sum Theorem for Distributional Query Complexity. CCC 2024: 16:1-16:30 - [c65]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Superconstant Inapproximability of Decision Tree Learning. COLT 2024: 2979-3010 - 2023
- [c64]Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou:
Multitask Learning via Shared Features: Algorithms and Hardness. COLT 2023: 747-772 - [c63]Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A strong composition theorem for junta complexity and the boosting of property testers. FOCS 2023: 1757-1777 - [c62]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Properly learning decision trees with queries is NP-hard. FOCS 2023: 2383-2407 - [c61]Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan:
Certification with an NP Oracle. ITCS 2023: 18:1-18:22 - [c60]Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, Mo Tiwari:
Harnessing the power of choices in decision tree learning. NeurIPS 2023 - [c59]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Single-Pass Streaming Algorithms for Correlation Clustering. SODA 2023: 819-849 - [c58]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Superpolynomial lower bounds for decision tree learning and testing. SODA 2023: 1962-1994 - [c57]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
Lifting Uniform Learners via Distributional Decomposition. STOC 2023: 1755-1767 - 2022
- [c56]Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan:
The Composition Complexity of Majority. CCC 2022: 19:1-19:26 - [c55]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
On the power of adaptivity in statistical adversaries. COLT 2022: 5030-5061 - [c54]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS 2022: 720-731 - [c53]Guy Blanc, Jane Lange, Li-Yang Tan:
Reconstructing Decision Trees. ICALP 2022: 24:1-24:17 - [c52]Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan:
A query-optimal algorithm for finding counterfactuals. ICML 2022: 2075-2090 - [c51]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
Popular decision tree algorithms are provably noise tolerant. ICML 2022: 2091-2106 - [c50]Milan Mossé, Harry Sha, Li-Yang Tan:
A Generalization of the Satisfiability Coding Lemma and Its Applications. SAT 2022: 9:1-9:18 - [c49]Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan:
The query complexity of certification. STOC 2022: 623-636 - 2021
- [c48]Rocco A. Servedio, Li-Yang Tan:
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM 2021: 37:1-37:18 - [c47]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. APPROX-RANDOM 2021: 45:1-45:16 - [c46]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. CCC 2021: 6:1-6:30 - [c45]Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan:
Tradeoffs for small-depth Frege proofs. FOCS 2021: 445-456 - [c44]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Properly learning decision trees in almost polynomial time. FOCS 2021: 920-929 - [c43]Victor Lecomte, Li-Yang Tan:
Sharper bounds on the Fourier concentration of DNFs. FOCS 2021: 930-941 - [c42]Guy Blanc, Jane Lange, Li-Yang Tan:
Learning Stochastic Decision Trees. ICALP 2021: 30:1-30:16 - [c41]Guy Blanc, Jane Lange, Li-Yang Tan:
Provably efficient, succinct, and precise explanations. NeurIPS 2021: 6129-6141 - [c40]Moses Charikar, Weiyun Ma, Li-Yang Tan:
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity. PODC 2021: 431-433 - [c39]Guy Blanc, Jane Lange, Li-Yang Tan:
Query strategies for priced information, revisited. SODA 2021: 1638-1650 - 2020
- [c38]Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan:
Non-malleability Against Polynomial Tampering. CRYPTO (3) 2020: 97-126 - [c37]Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan:
The Power of Many Samples in Query Complexity. ICALP 2020: 9:1-9:18 - [c36]Guy Blanc, Jane Lange, Li-Yang Tan:
Provable guarantees for decision tree induction: the agnostic setting. ICML 2020: 941-949 - [c35]Guy Blanc, Jane Lange, Li-Yang Tan:
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. ITCS 2020: 44:1-44:44 - [c34]Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan:
Estimating decision tree learnability with polylogarithmic sample complexity. NeurIPS 2020 - [c33]Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan:
Universal guarantees for decision tree induction via a higher-order splitting criterion. NeurIPS 2020 - [c32]Moses Charikar, Weiyun Ma, Li-Yang Tan:
Unconditional Lower Bounds for Adaptive Massively Parallel Computation. SPAA 2020: 141-151 - [c31]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Gaussian PTFs via local hyperconcentration. STOC 2020: 1170-1183 - 2019
- [c30]Rocco A. Servedio, Li-Yang Tan:
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. APPROX-RANDOM 2019: 45:1-45:23 - [c29]Rocco A. Servedio, Li-Yang Tan:
Pseudorandomness for read-k DNF formulas. SODA 2019: 621-638 - [c28]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling polytopes. STOC 2019: 614-625 - 2018
- [c27]Rocco A. Servedio, Li-Yang Tan:
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. APPROX-RANDOM 2018: 56:1-56:20 - [c26]Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. FOCS 2018: 826-837 - 2017
- [c25]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM 2017: 38:1-38:21 - [c24]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the Query Complexity of Non-Adaptive Junta Testing. CCC 2017: 26:1-26:19 - [c23]Rocco A. Servedio, Li-Yang Tan:
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. FOCS 2017: 813-823 - [c22]Rocco A. Servedio, Li-Yang Tan:
Fooling Intersections of Low-Weight Halfspaces. FOCS 2017: 824-835 - [c21]Rocco A. Servedio, Li-Yang Tan:
What Circuit Classes Can Be Learned with Non-Trivial Savings?. ITCS 2017: 30:1-30:21 - 2016
- [c20]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. STOC 2016: 612-625 - [c19]Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC 2016: 644-657 - 2015
- [c18]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning Circuits with few Negations. APPROX-RANDOM 2015: 512-527 - [c17]Rocco A. Servedio, Li-Yang Tan, John Wright:
Adaptivity Helps for Testing Juntas. CCC 2015: 264-279 - [c16]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. FOCS 2015: 1030-1048 - [c15]Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan:
Algorithmic Signaling of Features in Auction Design. SAGT 2015: 150-162 - [c14]Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer:
Approximate resilience, monotonicity, and the complexity of agnostic learning. SODA 2015: 498-511 - [c13]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. STOC 2015: 519-528 - 2014
- [c12]Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan:
A Composition Theorem for Parity Kill Number. CCC 2014: 144-154 - [c11]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New Algorithms and Lower Bounds for Monotonicity Testing. FOCS 2014: 286-295 - [c10]Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan:
On DNF Approximators for Monotone Boolean Functions. ICALP (1) 2014: 235-246 - [c9]Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou:
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. SODA 2014: 1644-1658 - 2013
- [c8]Dominik Scheder, Li-Yang Tan:
On the Average Sensitivity and Density of k-CNF Formulas. APPROX-RANDOM 2013: 683-698 - [c7]Eric Blais, Li-Yang Tan:
Approximating Boolean Functions with Depth-2 Circuits. CCC 2013: 74-85 - [c6]Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Learning Sums of Independent Integer Random Variables. FOCS 2013: 217-226 - [c5]Ryan O'Donnell, Li-Yang Tan:
A Composition Theorem for the Fourier Entropy-Influence Conjecture. ICALP (1) 2013: 780-791 - 2012
- [c4]Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. COLT 2012: 14.1-14.19 - 2010
- [c3]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. CCC 2010: 211-222 - [c2]Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. STOC 2010: 533-542 - 2005
- [c1]Aaron Stump, Li-Yang Tan:
The Algebra of Equality Proofs. RTA 2005: 469-483
Informal and Other Publications
- 2024
- [i71]Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A Strong Direct Sum Theorem for Distributional Query Complexity. CoRR abs/2405.16340 (2024) - [i70]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Superconstant Inapproximability of Decision Tree Learning. CoRR abs/2407.01402 (2024) - [i69]Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan:
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem. CoRR abs/2409.11597 (2024) - [i68]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Fast decision tree learning solves hard coding-theoretic problems. CoRR abs/2409.13096 (2024) - 2023
- [i67]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
Lifting uniform learners via distributional decomposition. CoRR abs/2303.16208 (2023) - [i66]Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers. CoRR abs/2307.04039 (2023) - [i65]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Properly Learning Decision Trees with Queries Is NP-Hard. CoRR abs/2307.04093 (2023) - [i64]Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, Mo Tiwari:
Harnessing the Power of Choices in Decision Tree Learning. CoRR abs/2310.01551 (2023) - 2022
- [i63]Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan:
The Query Complexity of Certification. CoRR abs/2201.07736 (2022) - [i62]Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan:
The composition complexity of majority. CoRR abs/2205.02374 (2022) - [i61]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR abs/2205.03710 (2022) - [i60]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
Popular decision tree algorithms are provably noise tolerant. CoRR abs/2206.08899 (2022) - [i59]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Open Problem: Properly learning decision trees in polynomial time? CoRR abs/2206.14431 (2022) - [i58]Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan:
A Query-Optimal Algorithm for Finding Counterfactuals. CoRR abs/2207.07072 (2022) - [i57]Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou:
Multitask Learning via Shared Features: Algorithms and Hardness. CoRR abs/2209.03112 (2022) - [i56]Caleb Koch, Carmen Strassle, Li-Yang Tan:
Superpolynomial Lower Bounds for Decision Tree Learning and Testing. CoRR abs/2210.06375 (2022) - [i55]Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan:
Certification with an NP Oracle. CoRR abs/2211.02257 (2022) - 2021
- [i54]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 abs/2102.05019 (2021) - [i53]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane:
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR abs/2103.07809 (2021) - [i52]Guy Blanc, Jane Lange, Li-Yang Tan:
Learning stochastic decision trees. CoRR abs/2105.03594 (2021) - [i51]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Decision tree heuristics can fail, even in the smoothed setting. CoRR abs/2107.00819 (2021) - [i50]Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021) - [i49]Victor Lecomte, Li-Yang Tan:
Sharper bounds on the Fourier concentration of DNFs. CoRR abs/2109.04525 (2021) - [i48]Guy Blanc, Jane Lange, Li-Yang Tan:
Provably efficient, succinct, and precise explanations. CoRR abs/2111.01576 (2021) - [i47]Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan:
Tradeoffs for small-depth Frege proofs. CoRR abs/2111.07483 (2021) - [i46]Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
On the power of adaptivity in statistical adversaries. CoRR abs/2111.10352 (2021) - [i45]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. TR21 (2021) - 2020
- [i44]Moses Charikar, Weiyun Ma, Li-Yang Tan:
New lower bounds for Massively Parallel Computation from query complexity. CoRR abs/2001.01146 (2020) - [i43]Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan:
The Power of Many Samples in Query Complexity. CoRR abs/2002.10654 (2020) - [i42]Guy Blanc, Jane Lange, Li-Yang Tan:
Provable guarantees for decision tree induction: the agnostic setting. CoRR abs/2006.00743 (2020) - [i41]Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan:
Universal guarantees for decision tree induction via a higher-order splitting criterion. CoRR abs/2010.08633 (2020) - [i40]Guy Blanc, Jane Lange, Li-Yang Tan:
Query strategies for priced information, revisited. CoRR abs/2010.11381 (2020) - [i39]Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan:
Estimating decision tree learnability with polylogarithmic sample complexity. CoRR abs/2011.01584 (2020) - [i38]Guy Blanc, Jane Lange, Li-Yang Tan:
Testing and reconstruction via decision trees. CoRR abs/2012.08735 (2020) - [i37]Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan:
Non-Malleability against Polynomial Tampering. Electron. Colloquium Comput. Complex. TR20 (2020) - [i36]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. TR20 (2020) - [i35]Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan:
Non-Malleability against Polynomial Tampering. IACR Cryptol. ePrint Arch. 2020: 147 (2020) - 2019
- [i34]Guy Blanc, Jane Lange, Li-Yang Tan:
Top-down induction of decision trees: rigorous guarantees and inherent limitations. CoRR abs/1911.07375 (2019) - [i33]Guy Blanc, Jane Lange, Li-Yang Tan:
Constructive derandomization of query algorithms. CoRR abs/1912.03042 (2019) - [i32]Guy Blanc, Jane Lange, Li-Yang Tan:
Top-down induction of decision trees: rigorous guarantees and inherent limitations. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i31]Rocco A. Servedio, Li-Yang Tan:
Deterministic search for CNF satisfying assignments in almost polynomial time. CoRR abs/1801.03588 (2018) - [i30]Rocco A. Servedio, Li-Yang Tan:
Improved pseudorandom generators from pseudorandom multi-switching lemmas. CoRR abs/1801.03590 (2018) - [i29]Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. CoRR abs/1802.07673 (2018) - [i28]Rocco A. Servedio, Li-Yang Tan:
Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. CoRR abs/1803.04553 (2018) - [i27]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. CoRR abs/1808.04035 (2018) - [i26]Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - [i25]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. Electron. Colloquium Comput. Complex. TR18 (2018) - [i24]Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. IACR Cryptol. ePrint Arch. 2018: 207 (2018) - 2017
- [i23]Rocco A. Servedio, Li-Yang Tan:
Fooling intersections of low-weight halfspaces. CoRR abs/1704.04855 (2017) - [i22]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. CoRR abs/1704.06314 (2017) - [i21]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR abs/1706.05556 (2017) - [i20]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. TR17 (2017) - 2015
- [i19]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An average-case depth hierarchy theorem for Boolean circuits. CoRR abs/1504.03398 (2015) - [i18]Eric Blais, Li-Yang Tan, Andrew Wan:
An inequality for the Fourier spectrum of parity decision trees. CoRR abs/1506.01055 (2015) - [i17]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. CoRR abs/1509.07476 (2015) - [i16]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An average-case depth hierarchy theorem for Boolean circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i15]Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer:
Approximate resilience, monotonicity, and the complexity of agnostic learning. CoRR abs/1405.5268 (2014) - [i14]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. CoRR abs/1410.8420 (2014) - [i13]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New algorithms and lower bounds for monotonicity testing. CoRR abs/1412.5655 (2014) - [i12]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries. CoRR abs/1412.5657 (2014) - [i11]Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i10]Ryan O'Donnell, Li-Yang Tan:
A composition theorem for the Fourier Entropy-Influence conjecture. CoRR abs/1304.1347 (2013) - [i9]Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, Yu Zhao:
A composition theorem for parity kill number. CoRR abs/1312.2143 (2013) - [i8]Eric Blais, Li-Yang Tan:
Approximating Boolean functions with depth-2 circuits. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i7]Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
On the Distribution of the Fourier Spectrum of Halfspaces. CoRR abs/1202.6680 (2012) - [i6]Li-Yang Tan:
Analysis of Boolean Functions. CoRR abs/1205.0314 (2012) - [i5]Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright:
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover. CoRR abs/1210.5648 (2012) - [i4]Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou:
Hypercontractive inequalities via SOS, with an application to Vertex-Cover. CoRR abs/1212.5324 (2012) - [i3]Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - 2009
- [i2]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. CoRR abs/0909.4727 (2009) - [i1]Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Average sensitivity and noise sensitivity of polynomial threshold functions. CoRR abs/0909.5011 (2009)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-18 20:25 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
