# Nicholas J. A. Harvey

According to our database

Collaborative distances:

^{1}, Nicholas J. A. Harvey authored at least 55 papers between 2003 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2020

An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles.

SIAM J. Comput., 2020

Online mirror descent and dual averaging: keeping pace in the dynamic case.

CoRR, 2020

Optimal anytime regret with two experts.

CoRR, 2020

2019

A General Framework for Graph Sparsification.

SIAM J. Comput., 2019

Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks.

J. Mach. Learn. Res., 2019

Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent.

CoRR, 2019

Tight analyses for non-smooth stochastic gradient descent.

Proceedings of the Conference on Learning Theory, 2019

2018

Submodular Functions: Learnability, Structure, and Optimization.

SIAM J. Comput., 2018

Greedy and Local Ratio Algorithms in the MapReduce Model.

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Computing the Independence Polynomial: from the Tree Threshold down to the Roots.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes.

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

Rainbow Hamilton cycles and lopsidependency.

Discret. Math., 2017

Matroids Hitting Sets and Unsupervised Dependency Grammar Induction.

CoRR, 2017

Nearly-tight VC-dimension bounds for piecewise linear neural networks.

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Sparse Sums of Positive Semidefinite Matrices.

ACM Trans. Algorithms, 2016

Computing the independence polynomial in Shearer's region for the LLL.

CoRR, 2016

Generating Random Spanning Trees via Fast Matrix Multiplication.

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015

Counter Stacks and the Elusive Working Set.

login Usenix Mag., 2015

A note on the discrepancy of matrices with bounded row and column sums.

Discret. Math., 2015

An Algorithmic Proof of the Lopsided Lovasz Local Lemma.

CoRR, 2015

Approximating Hit Rate Curves using Streaming Algorithms.

Proceedings of the Approximation, 2015

2014

UNO is hard, even for a single player.

Theor. Comput. Sci., 2014

Pipage Rounding, Pessimistic Estimators and Matrix Concentration.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Characterizing Storage Workloads with Counter Stacks.

Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, 2014

Near-Optimal Herding.

Proceedings of The 27th Conference on Learning Theory, 2014

Discrepancy Without Partial Colorings.

Proceedings of the Approximation, 2014

2012

Learning Submodular Functions.

Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2012

2011

On the complexity of reconfiguration problems.

Theor. Comput. Sci., 2011

On Disjoint Common Bases in Two Matroids.

SIAM J. Discret. Math., 2011

2010

Graph Sparsification by Edge-Connectivity and Random Spanning Trees

CoRR, 2010

2009

Algebraic Algorithms for Matching and Matroid Problems.

SIAM J. Comput., 2009

A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem

CoRR, 2009

Approximating submodular functions everywhere.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Matchings, matroids and submodular functions.

PhD thesis, 2008

Matroid intersection, pointer chasing, and Young's seminormal representation of

*S*._{n}
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Streaming algorithms for estimating entropy.

Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Sketching and Streaming Entropy via Approximation Theory.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Iteratively constructing preconditioners via the conjugate gradient method.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

An algebraic algorithm for weighted linear matroid intersection.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

A "Chicken & Egg" Network Coding Problem.

Proceedings of the IEEE International Symposium on Information Theory, 2007

Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs.

Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

2006

On the capacity of information networks.

IEEE Trans. Inf. Theory, 2006

Semi-matchings for bipartite graphs and load balancing.

J. Algorithms, 2006

Algebraic Structures and Algorithms for Matching and Matroid Problems (Preliminary Version)

CoRR, 2006

The complexity of matrix completion.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On the capacity of information networks.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Lower bounds for asymmetric communication channels and distributed source coding.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Algebraic Structures and Algorithms for Matching and Matroid Problems.

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Deterministic network coding by matrix completion.

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Deterministic SkipNet.

Inf. Process. Lett., 2004

Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

FUSE: Lightweight Guaranteed Distributed Failure Notification.

Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI 2004), 2004

2003

SkipNet: A Scalable Overlay Network with Practical Locality Properties.

Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, 2003

Brief announcement: deterministic skipnet.

Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Efficient Recovery from Organizational Disconnects in SkipNet.

Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003