Daniel M. Kane

According to our database1, Daniel M. Kane authored at least 103 papers between 2005 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
Testing Bayesian Networks.
IEEE Trans. Inf. Theory, 2020

Optimal Testing of Discrete Distributions with High Probability.
Electron. Colloquium Comput. Complex., 2020

A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise.
CoRR, 2020

Prisoners, Rooms, and Lightswitches.
CoRR, 2020

Outlier Robust Mean Estimation with Subgaussian Rates via Stability.
CoRR, 2020

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise.
CoRR, 2020

Robust Learning of Mixtures of Gaussians.
CoRR, 2020

Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals.
CoRR, 2020

List-Decodable Mean Estimation via Iterative Multi-Filtering.
CoRR, 2020

Robustly Learning any Clusterable Mixture of Gaussians.
CoRR, 2020

Point Location and Active Learning: Learning Halfspaces Almost Optimally.
CoRR, 2020

Noise-tolerant, Reliable Active Classification with Comparison Queries.
Proceedings of the Conference on Learning Theory, 2020

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks.
Proceedings of the Conference on Learning Theory, 2020

2019
Three-dimensional Floorplan Representations by Using Corner Links and Partial Order.
ACM Trans. Design Autom. Electr. Syst., 2019

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes.
SIAM J. Comput., 2019

Robust Estimators in High-Dimensions Without the Computational Intractability.
SIAM J. Comput., 2019

Near-optimal Linear Decision Trees for k-SUM and Related Problems.
J. ACM, 2019

Recent Advances in Algorithmic High-Dimensional Robust Statistics.
CoRR, 2019

The Power of Comparisons for Actively Learning Linear Classifiers.
CoRR, 2019

Waring's Theorem for Binary Powers.
Comb., 2019

Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications).
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Testing of Distributions via Sample Permutations.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

The Orthogonal Vectors Conjecture for Branching Programs and Formulas.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Sever: A Robust Meta-Algorithm for Stochastic Optimization.
Proceedings of the 36th International Conference on Machine Learning, 2019

Learning Ising Models with Independent Failures.
Proceedings of the Conference on Learning Theory, 2019

Testing Identity of Multidimensional Histograms.
Proceedings of the Conference on Learning Theory, 2019

Communication and Memory Efficient Testing of Discrete Distributions.
Proceedings of the Conference on Learning Theory, 2019

The Optimal Approximation Factor in Density Estimation.
Proceedings of the Conference on Learning Theory, 2019

2018
Pseudorandomness via the Discrete Fourier Transform.
SIAM J. Comput., 2018

Generalized comparison trees for point-location problems.
Electron. Colloquium Comput. Complex., 2018

Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications).
Electron. Colloquium Comput. Complex., 2018

The entropy of lies: playing twenty questions with a liar.
CoRR, 2018

Quantum Money from Modular Forms.
CoRR, 2018

Learning geometric concepts with nasty noise.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

List-decodable robust mean estimation and learning mixtures of spherical gaussians.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Testing conditional independence of discrete distributions.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Robust Learning of Fixed-Structure Bayesian Networks.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
Labeling the complete bipartite graph with no zero cycles.
Electron. Colloquium Comput. Complex., 2017

Active classification with comparison queries.
Electron. Colloquium Comput. Complex., 2017

On Communication Complexity of Classification Problems.
Electron. Colloquium Comput. Complex., 2017

A Polynomial Restriction Lemma with Applications.
Electron. Colloquium Comput. Complex., 2017

Sharp Bounds for Generalized Uniformity Testing.
Electron. Colloquium Comput. Complex., 2017

A Bound on Partitioning Clusters.
Electron. J. Comb., 2017

Being Robust (in High Dimensions) Can Be Practical.
Proceedings of the 34th International Conference on Machine Learning, 2017

Near-Optimal Closeness Testing of Discrete Histogram Distributions.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Robust Polynomial Regression up to the Information Theoretic Limit.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Learning Multivariate Log-concave Distributions.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
Big-Key Symmetric Encryption: Resisting Key Exfiltration.
IACR Cryptol. ePrint Arch., 2016

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures.
Electron. Colloquium Comput. Complex., 2016

A New Approach for Testing Properties of Discrete Distributions.
Electron. Colloquium Comput. Complex., 2016

Efficient Robust Proper Learning of Log-concave Distributions.
CoRR, 2016

A Short Implicant of a CNF Formula with Many Satisfying Assignments.
Algorithmica, 2016

The fourier transform of poisson multinomial distributions and its algorithmic applications.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Fourier-Sparse Interpolation without a Frequency Gap.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time.
Proceedings of the 29th Conference on Learning Theory, 2016

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables.
Proceedings of the 29th Conference on Learning Theory, 2016

3D floorplan representations: Corner links and partial order.
Proceedings of the 2016 IEEE International 3D Systems Integration Conference, 2016

2015
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks.
IACR Cryptol. ePrint Arch., 2015

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits.
Electron. Colloquium Comput. Complex., 2015

Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables.
CoRR, 2015

Central limit theorems for some set partition statistics.
Adv. Appl. Math., 2015

Testing Identity of Structured Distributions.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Sparser Johnson-Lindenstrauss Transforms.
J. ACM, 2014

Pseudorandomness for concentration bounds and signed majorities.
CoRR, 2014

The correct exponent for the Gotsman-Linial Conjecture.
Comput. Complex., 2014

The average sensitivity of an intersection of half spaces.
Proceedings of the Symposium on Theory of Computing, 2014

A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta.
Theory Comput., 2013

A Short Implicant of CNFs with Relatively Many Satisfying Assignments.
Electron. Colloquium Comput. Complex., 2013

A PRG for lipschitz functions of polynomials with applications to sparsest cut.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching.
Proceedings of the COLT 2013, 2013

2012
A Low-Depth Monotone Function that is not an Approximate Junta
CoRR, 2012

A Structure Theorem for Poorly Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions.
CoRR, 2012

Counting Arbitrary Subgraphs in Data Streams.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Tight Bounds for Testing k-Linearity.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Quantum interpolation of polynomials.
Quantum Inf. Comput., 2011

The Gaussian Surface Area and Noise Sensitivity of Degree-<i>d</i> Polynomial Threshold Functions.
Comput. Complex., 2011

Fast moment estimation in data streams in optimal space.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

A Small PRG for Polynomial Threshold Functions of Gaussians.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

k-Independent Gaussians Fool Polynomial Threshold Functions.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Almost Optimal Explicit Johnson-Lindenstrauss Families.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
On Solving Games Constructed Using Both Short and Long Conjunctive Sums.
Integers, 2010

A Derandomized Sparse Johnson-Lindenstrauss Transform.
Electron. Colloquium Comput. Complex., 2010

A Sparser Johnson-Lindenstrauss Transform
CoRR, 2010

Unary Subset-Sum is in Logspace
CoRR, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

An optimal algorithm for the distinct elements problem.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

2009
Bounded Independence Fools Degree-2 Threshold Functions.
Electron. Colloquium Comput. Complex., 2009

The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials
CoRR, 2009

Dynamic ham-sandwich cuts in the plane.
Comput. Geom., 2009

The geometry of binary search trees.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A Pseudopolynomial Algorithm for Alexandrov's Theorem.
Proceedings of the Computational Geometry, 08.03. - 13.03.2009, 2009

2008
On the S<sub>n</sub>-Modules Generated by Partitions of a Given Shape.
Electron. J. Comb., 2008

2005
On the Complexity of Two-PlayerWin-Lose Games.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005


  Loading...