Sotabase

Career

· PhD in Computer Science, Columbia University
· Assistant Professor, Stanford University
· TTI Chicago
· Microsoft Research Fellow, UC Berkeley Simons Institute

Publications (84)

An Average-Case Depth Hierarchy Theorem for Boolean Circuits
IEEE Annual Symposium on Foundations of Computer Science · 2015
79
cited
New Algorithms and Lower Bounds for Monotonicity Testing
IEEE Annual Symposium on Foundations of Computer Science · 2014
70
cited
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
Symposium on the Theory of Computing · 2014
58
cited
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
2014
54
cited
Learning Sums of Independent Integer Random Variables
IEEE Annual Symposium on Foundations of Computer Science · 2013
53
cited
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
2010 IEEE 25th Annual Conference on Computational Complexity · 2009
49
cited
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
SIAM journal on computing (Print) · 2009
49
cited
Provably efficient, succinct, and precise explanations
Neural Information Processing Systems · 2021
39
cited
Non-Malleable Codes for Small-Depth Circuits
IEEE Annual Symposium on Foundations of Computer Science · 2018
35
cited
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Symposium on the Theory of Computing · 2010
33
cited
Learning circuits with few negations
Electron. Colloquium Comput. Complex. · 2014
33
cited
Settling the Query Complexity of Non-adaptive Junta Testing
Cybersecurity and Cyberforensics Conference · 2017
33
cited
Almost 3-Approximate Correlation Clustering in Constant Rounds
IEEE Annual Symposium on Foundations of Computer Science · 2022
32
cited
Approximate resilience, monotonicity, and the complexity of agnostic learning
ACM-SIAM Symposium on Discrete Algorithms · 2014
32
cited
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
Annual Conference Computational Learning Theory · 2012
28
cited
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
ACM-SIAM Symposium on Discrete Algorithms · 2012
28
cited
Top-down induction of decision trees: rigorous guarantees and inherent limitations
Electron. Colloquium Comput. Complex. · 2019
28
cited
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Symposium on the Theory of Computing · 2016
27
cited
Adaptivity Helps for Testing Juntas
Cybersecurity and Cyberforensics Conference · 2015
26
cited
The Algebra of Equality Proofs
International Conference on Rewriting Techniques and Applications · 2005
25
cited
Sotabase
Li-Yang Tan | Researcher Profile | Sotabase | Sotabase