Daniel Kane

Q: What Schools Are Affiliated With Daniel Kane

Daniel Kane is affiliated with the following schools: University of California, San Diego, Stanford University, Massachusetts Institute of Technology, Harvard University

Daniel Kane 's AcademicInfluence.com Rankings

Daniel Kane

Mathematics

#1345

World Rank

#2240

Historical Rank

#558

USA Rank

Measure Theory

#2718

World Rank

#3247

Historical Rank

#784

USA Rank

mathematics Degrees

Download Badge

Mathematics

Why Is Daniel Kane Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Daniel Mertz Kane is an American mathematician. He is an associate professor with a joint position in the Mathematics Department and the Computer Science and Engineering Department at the University of California, San Diego.

(See a Problem?)

Daniel Kane 's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Robust Estimators in High Dimensions without the Computational Intractability (2016) (407)
An optimal algorithm for the distinct elements problem (2010) (320)
Sparser Johnson-Lindenstrauss Transforms (2010) (319)
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018) (223)
Being Robust (in High Dimensions) Can Be Practical (2017) (216)
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016) (173)
On the exact space complexity of sketching and streaming small norms (2010) (160)
A New Approach for Testing Properties of Discrete Distributions (2016) (141)
Recent Advances in Algorithmic High-Dimensional Robust Statistics (2019) (138)
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently (2017) (122)
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017) (112)
Bounded Independence Fools Degree-2 Threshold Functions (2009) (105)
Fast moment estimation in data streams in optimal space (2010) (92)
Testing Identity of Structured Distributions (2014) (92)
On the complexity of two-player win-lose games (2005) (82)
The geometry of binary search trees (2009) (77)
Counting Arbitrary Subgraphs in Data Streams (2012) (75)
Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves (2013) (71)
Learning geometric concepts with nasty noise (2017) (69)
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks (2015) (69)
A Derandomized Sparse Johnson-Lindenstrauss Transform (2010) (65)
Testing Bayesian Networks (2016) (59)
Active Classification with Comparison Queries (2017) (58)
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions (2010) (55)
Almost Optimal Explicit Johnson-Lindenstrauss Families (2011) (55)
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits (2015) (54)
On the ranks of the 2-Selmer groups of twists of a given elliptic curve (2010) (54)
Testing Conditional Independence of Discrete Distributions (2017) (45)
Robust Learning of Fixed-Structure Bayesian Networks (2016) (42)
Pseudorandomness via the Discrete Fourier Transform (2015) (42)
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions (2015) (41)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks (2020) (40)
Fourier-Sparse Interpolation without a Frequency Gap (2016) (37)
Efficient Robust Proper Learning of Log-concave Distributions (2016) (37)
The fourier transform of poisson multinomial distributions and its algorithmic applications (2015) (36)
Big-Key Symmetric Encryption: Resisting Key Exfiltration (2016) (36)
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals (2020) (36)
The correct exponent for the Gotsman–Linial Conjecture (2012) (35)
New results on the least common multiple of consecutive integers (2008) (34)
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables (2015) (33)
Robustly Learning any Clusterable Mixture of Gaussians (2020) (33)
A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions (2012) (32)
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering (2019) (31)
A Small PRG for Polynomial Threshold Functions of Gaussians (2011) (31)
Outlier Robust Mean Estimation with Subgaussian Rates via Stability (2020) (31)
k-Independent Gaussians Fool Polynomial Threshold Functions (2010) (30)
Learning Multivariate Log-concave Distributions (2016) (29)
Robustly learning mixtures of k arbitrary Gaussians (2020) (27)
Near-Optimal Closeness Testing of Discrete Histogram Distributions (2017) (26)
A Pseudopolynomial Algorithm for Alexandrov's Theorem (2008) (26)
Near-optimal linear decision trees for k-SUM and related problems (2017) (26)
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time (2015) (26)
A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length (2012) (24)
Tight Bounds for Testing k-Linearity (2012) (23)
A PRG for lipschitz functions of polynomials with applications to sparsest cut (2012) (20)
The average sensitivity of an intersection of half spaces (2013) (19)
Noise-tolerant, Reliable Active Classification with Comparison Queries (2020) (19)
Closed expressions for averages of set partition statistics (2013) (19)
Resolution of a conjecture of Andrews and Lewis involving cranks of partitions (2004) (18)
Central limit theorems for some set partition statistics (2015) (18)
Communication and Memory Efficient Testing of Discrete Distributions (2019) (18)
The Power of Comparisons for Actively Learning Linear Classifiers (2019) (17)
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals (2021) (17)
Optimal testing of discrete distributions with high probability (2020) (17)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise (2020) (17)
Hardness of Learning Halfspaces with Massart Noise (2020) (16)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models (2020) (16)
Revisiting Norm Estimation in Data Streams (2008) (16)
Sharp Bounds for Generalized Uniformity Testing (2017) (16)
List-Decodable Mean Estimation via Iterative Multi-Filtering (2020) (16)
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin (2019) (15)
On Communication Complexity of Classification Problems (2017) (15)
Generalized base representations (2006) (15)
Private Testing of Distributions via Sample Permutations (2019) (15)
Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching (2013) (14)
Near-optimal Linear Decision Trees for k-SUM and Related Problems (2019) (14)
Robust Learning of Mixtures of Gaussians (2020) (14)
Noise Sensitivity of Polynomial Threshold Functions (2011) (13)
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes (2017) (13)
The Optimal Approximation Factor in Density Estimation (2019) (13)
Learning Ising Models with Independent Failures (2019) (13)
Testing Identity of Multidimensional Histograms (2018) (13)
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures (2020) (13)
Asymptotic Improvements of Lower Bounds for the Least Common Multiples of Arithmetic Progressions (2010) (12)
A Bound on Partitioning Clusters (2017) (12)
Small designs for path-connected spaces and path-connected homogeneous spaces (2011) (12)
Generalized comparison trees for point-location problems (2018) (12)
An elementary derivation of the asymptotics of partition functions (2006) (12)
Bounds on the Independence Required for Cuckoo Hashing (2013) (11)
Point Location and Active Learning: Learning Halfspaces Almost Optimally (2020) (10)
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise (2020) (10)
Statistical Query Lower Bounds for List-Decodable Linear Regression (2021) (10)
Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables (2015) (10)
A polynomial restriction lemma with applications (2017) (10)
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise (2020) (10)
Unary Subset-Sum is in Logspace (2010) (10)
List-Decodable Mean Estimation in Nearly-PCA Time (2020) (10)
Quantum Money from Modular Forms (2018) (9)
Realizable Learning is All You Need (2021) (9)
Clustering mixture models in almost-linear time via list-decodable mean estimation (2021) (9)
The Orthogonal Vectors Conjecture for Branching Programs and Formulas (2017) (9)
Quantum interpolation of polynomials (2009) (9)
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition (2021) (9)
Outlier-Robust Sparse Estimation via Non-Convex Optimization (2021) (9)
Minimal models of compact symplectic semitoric manifolds (2016) (9)
Robustness meets algorithms (2021) (9)
Robust Polynomial Regression up to the Information Theoretic Limit (2017) (9)
Waring’s Theorem for Binary Powers (2018) (8)
Forster Decomposition and Learning Halfspaces with Noise (2021) (8)
Robust Sparse Mean Estimation via Sum of Squares (2022) (8)
Non-Gaussian Component Analysis via Lattice Basis Reduction (2021) (8)
Efficiently learning halfspaces with Tsybakov noise (2021) (7)
Quantum interpolation of polynomilas (2011) (7)
A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting (2014) (7)
Boosting in the Presence of Massart Noise (2021) (7)
Cryptographic Hardness of Learning Halfspaces with Massart Noise (2022) (7)
Classifying Toric and Semitoric Fans by Lifting Equations from SL2(Z) (2015) (7)
Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2005) (6)
The entropy of lies: playing twenty questions with a liar (2018) (6)
On Elliptic Curves, the ABC Conjecture, and Polynomial Threshold Functions A dissertation presented (2011) (6)
Learning general halfspaces with general Massart noise under the Gaussian distribution (2021) (6)
Improved bounds on the number of ways of expressing as a binomial coefficient. (2007) (6)
Agnostic Proper Learning of Halfspaces under Gaussian Marginals (2021) (6)
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland (2017) (5)
Streaming Algorithms for High-Dimensional Robust Statistics (2022) (5)
Quantum Money from Quaternion Algebras (2021) (5)
On the φ-Selmer groups of the elliptic curves y 2 = x 3 − Dx (2016) (5)
Canonical Projective Embeddings of the Deligne–Lusztig Curves Associated to 2A2, 2B2, and 2G2 (2010) (5)
Pseudorandomness for concentration bounds and signed majorities (2014) (5)
Minimal S-Universality Criteria May Vary in Size (2011) (5)
Best Possible Densities of Dickson m-Tuples, as a Consequence of Zhang–Maynard–Tao (2014) (4)
An Asymptotic for the Number of Solutions to Linear Equations in Prime Numbers from Specified Chebotarev Classes (2010) (4)
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in and Logarithmic in n (2018) (4)
Labeling the complete bipartite graph with no zero cycles (2017) (4)
A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions (2017) (4)
Hardness of Learning a Single Neuron with Adversarial Label Noise (2022) (4)
New bounds on the number of representation of as a binomial coefficient. (2004) (4)
On the Joint Distribution Of Sel φ ( E / Q ) and Sel φ ( E ′ / Q ) in Quadratic Twist Families (2013) (4)
A Sparser Johnson-Lindenstrauss Transform (2010) (4)
The Sample Complexity of Robust Covariance Testing (2020) (4)
Computational-Statistical Gaps in Reinforcement Learning (2022) (4)
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions (2022) (3)
Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications) (2018) (3)
Threshold Phenomena in Learning Halfspaces with Massart Noise (2021) (3)
Bounded Memory Active Learning through Enriched Queries (2021) (3)
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering (2022) (3)
The correct exponent for the Gotsman–Linial Conjecture (2013) (3)
A Short Implicant of CNFs with Relatively Many Satisfying Assignments (2013) (3)
Dynamic ham-sandwich cuts in the plane (2009) (3)
A PROOF OF ANDREWS’ CONJECTURE ON PARTITIONS WITH NO SHORT SEQUENCES (2012) (3)
Minimal $\mathcal{S}$-universality criteria may vary in size (2013) (3)
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning (2022) (3)
ASYMPTOTICS FOR WILF ’ S PARTITIONS WITH DISTINCT MULTIPLICITIES (2012) (3)
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals (2023) (2)
Dropping Lowest Grades (2006) (2)
Testing Properties of Linear Functions (2012) (2)
Ergodic Properties of a Class of Discrete Abelian Group Extensions of Rank-One Transformations (2008) (2)
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models (2022) (1)
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n (2018) (1)
A Pseudorandom Generator for Polynomial Threshold Functions with Subpolynomial Seed Length (2013) (1)
On Solving Games Constructed Using Both Short and Long Conjunctive Sums (2010) (1)
On a Problem Relating to the ABC Conjecture (2011) (1)
Canonical Projective Embeddings of the Deligne-Lusztig Curves Associated to 2 A 2 , 2 B 2 and 2 G 2 (2015) (1)
The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials (2009) (1)
Near-Optimal Bounds for Testing Histogram Distributions (2022) (1)
On the Number of ABC Solutions with Restricted Radical Sizes (2011) (1)
Robust High-Dimensional Statistics (2020) (1)
Asymptotics of McKay numbers for Sn (2007) (1)
On the Sn-Modules Generated by Partitions of a Given Shape (2008) (0)
On the Joint Distribution Of $\mathrm{Sel}_\phi(E/\mathbb{Q})$ and $\mathrm{Sel}_{\hat\phi}(E^\prime/\mathbb{Q})$ in Quadratic Twist Families (2017) (0)
On lower bounds on the size of sums-of-squares formulas (2008) (0)
Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016) (2016) (0)
Gaussian Mean Testing Made Simple (2022) (0)
Do PAC-Learners Learn the Marginal Distribution? (2023) (0)
A Short Implicant of a CNF Formula with Many Satisfying Assignments (2014) (0)
A Low-Depth Monotone Function that is not an Approximate Junta (2012) (0)
On the Crossing Number of Complete Graphs with an Uncrossed Hamiltonian Cycle (2013) (0)
Efficient Testable Learning of Halfspaces with Adversarial Label Noise (2023) (0)
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA (2023) (0)
SQ Lower Bounds for Learning Single Neurons with Massart Noise (2022) (0)
On the φ-Selmer groups of the elliptic curves y = x −Dx (2013) (0)
An example concerning set addition in F_2^n (2017) (0)
ON THE NUMBER OF WAYS OF WRITING T AS A PRODUCT OF FACTORIALS (2005) (0)
On the ${\cal S}_{n}$-Modules Generated by Partitions of a Given Shape (2008) (0)
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm (2023) (0)
Weak mixing of a transformation similar to Pascal (2007) (0)
A Structure Theorem for Poorly (2012) (0)
Table of Contents (2020) (0)
The William Lowell Putnam Mathematical Competition 2001–2016 (2020) (0)
Dynamic ham-sandwich cuts in the plane Citation (2009) (0)
Complexity of Classification Problems (2019) (0)
An Example Concerning Set Addition in $$\mathbb{F}_2^n$$F2n (2018) (0)
Algebra & Number Theory (2013) (0)
N ov 2 01 8 Degreed Chow Parameters Robustly Determine Degreed PTFs ( and Algorithmic Applications ) (2018) (0)
Fe b 20 19 Learning Ising Models with Independent Failures (2019) (0)
Closed expressions for averages of set partition statistics (2014) (0)
Weak Mixing of a Transformation Similar to (2006) (0)
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points (2022) (0)
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta (2013) (0)
Prisoners, Rooms, and Lightswitches (2020) (0)
Asymptotic Results for the Queen Packing Problem (2017) (0)

This paper list is powered by the following services:

Other Resources About Daniel Kane

en.wikipedia.org

What Schools Are Affiliated With Daniel Kane ?

Daniel Kane is affiliated with the following schools:

Daniel Kane 's Academic­Influence.com Rankings