Nicholas J. A. Harvey

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Online Mirror Descent and Dual Averaging: Keeping Pace in the Dynamic Case.

[BibT_eX]

[DOI]

Huang Fang

Victor S. Portella

Michael P. Friedlander

J. Mach. Learn. Res., 2022

Continuous Prediction with Experts' Advice.

[BibT_eX]

[DOI]

Victor Sanches Portella

CoRR, 2022

Efficient and Optimal Fixed-Time Regret with Two Experts.

[BibT_eX]

[DOI]

Laura Greenstreet

Victor Sanches Portella

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2020

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes.

[BibT_eX]

[DOI]

Hassan Ashtiani

Shai Ben-David

Abbas Mehrabian

Yaniv Plan

J. ACM, 2020

Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses.

[BibT_eX]

[DOI]

Yihan Zhou

Victor S. Portella

Mark Schmidt

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds.

[BibT_eX]

[DOI]

Tasuku Soma

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Optimal anytime regret for two experts.

[BibT_eX]

[DOI]

Edwin A. Perkins

Sikander Randhawa

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A General Framework for Graph Sparsification.

[BibT_eX]

[DOI]

Wai Shing Fung

Ramesh Hariharan

Debmalya Panigrahi

SIAM J. Comput., 2019

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

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2019

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

[BibT_eX]

[DOI]

Sikander Randhawa

CoRR, 2019

Tight analyses for non-smooth stochastic gradient descent.

[BibT_eX]

[DOI]

Yaniv Plan

Sikander Randhawa

Proceedings of the Conference on Learning Theory, 2019

2018

Submodular Functions: Learnability, Structure, and Optimization.

[BibT_eX]

[DOI]

Maria-Florina Balcan

SIAM J. Comput., 2018

Greedy and Local Ratio Algorithms in the MapReduce Model.

[BibT_eX]

[DOI]

Paul Liu

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.

[BibT_eX]

[DOI]

Piyush Srivastava

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.

[BibT_eX]

[DOI]

Hassan Ashtiani

Shai Ben-David

Abbas Mehrabian

Yaniv Plan

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.

[BibT_eX]

[DOI]

Discret. Math., 2017

Matroids Hitting Sets and Unsupervised Dependency Grammar Induction.

[BibT_eX]

[DOI]

David R. Karger

Virginia Savova

Leonid Peshkin

CoRR, 2017

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

[BibT_eX]

[DOI]

Nick Harvey

Marcel Kenji de Carli Silva

Abbas Mehrabian

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Sparse Sums of Positive Semidefinite Matrices.

[BibT_eX]

[DOI]

Cristiane M. Sato

ACM Trans. Algorithms, 2016

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

[BibT_eX]

[DOI]

Piyush Srivastava

CoRR, 2016

Generating Random Spanning Trees via Fast Matrix Multiplication.

[BibT_eX]

[DOI]

Keyulu Xu

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015

Counter Stacks and the Elusive Working Set.

[BibT_eX]

[DOI]

Jake Wires

Stephen Ingram

Zachary Drudi

Andrew Warfield

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

[BibT_eX]

[DOI]

Discret. Math., 2015

An Algorithmic Proof of the Lopsided Lovasz Local Lemma.

[BibT_eX]

[DOI]

CoRR, 2015

Approximating Hit Rate Curves using Streaming Algorithms.

[BibT_eX]

[DOI]

Zachary Drudi

Stephen Ingram

Andrew Warfield

Jake Wires

Proceedings of the Approximation, 2015

2014

UNO is hard, even for a single player.

[BibT_eX]

[DOI]

Erik D. Demaine

Martin L. Demaine

Ryuhei Uehara

Takeaki Uno

Yushi Uno

Theor. Comput. Sci., 2014

Pipage Rounding, Pessimistic Estimators and Matrix Concentration.

[BibT_eX]

[DOI]

Neil Olver

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

Characterizing Storage Workloads with Counter Stacks.

[BibT_eX]

[DOI]

Jake Wires

Stephen Ingram

Zachary Drudi

Andrew Warfield

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

Near-Optimal Herding.

[BibT_eX]

[DOI]

Nick Harvey

Samira Samadi

Proceedings of The 27th Conference on Learning Theory, 2014

Discrepancy Without Partial Colorings.

[BibT_eX]

[DOI]

Roy Schwartz

Mohit Singh

Proceedings of the Approximation, 2014

2012

Learning Submodular Functions.

[BibT_eX]

[DOI]

Maria-Florina Balcan

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

2011

On the complexity of reconfiguration problems.

[BibT_eX]

[DOI]

Takehiro Ito

Erik D. Demaine

Christos H. Papadimitriou

Martha Sideri

Ryuhei Uehara

Yushi Uno

Theor. Comput. Sci., 2011

On Disjoint Common Bases in Two Matroids.

[BibT_eX]

[DOI]

Tamás Király

Lap Chi Lau

SIAM J. Discret. Math., 2011

2010

Graph Sparsification by Edge-Connectivity and Random Spanning Trees

[BibT_eX]

[DOI]

Wai Shing Fung

CoRR, 2010

2009

Algebraic Algorithms for Matching and Matroid Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem

[BibT_eX]

[DOI]

Michel X. Goemans

Kamal Jain

Mohit Singh

CoRR, 2009

Approximating submodular functions everywhere.

[BibT_eX]

[DOI]

Michel X. Goemans

Satoru Iwata

Vahab S. Mirrokni

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

2008

Matchings, matroids and submodular functions.

[BibT_eX]

[DOI]

PhD thesis, 2008

Matroid intersection, pointer chasing, and Young's seminormal representation of <i>S<sub>n</sub></i>.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Streaming algorithms for estimating entropy.

[BibT_eX]

[DOI]

Jelani Nelson

Krzysztof Onak

Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Sketching and Streaming Entropy via Approximation Theory.

[BibT_eX]

[DOI]

Jelani Nelson

Krzysztof Onak

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

2007

Iteratively constructing preconditioners via the conjugate gradient method.

[BibT_eX]

[DOI]

John Dunagan

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

An algebraic algorithm for weighted linear matroid intersection.

[BibT_eX]

[DOI]

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

A "Chicken & Egg" Network Coding Problem.

[BibT_eX]

[DOI]

Robert Kleinberg

Chandra Nair

Yunnan Wu

Proceedings of the IEEE International Symposium on Information Theory, 2007

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

[BibT_eX]

[DOI]

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

2006

On the capacity of information networks.

[BibT_eX]

[DOI]

Robert D. Kleinberg

April Rasala Lehman

IEEE Trans. Inf. Theory, 2006

Semi-matchings for bipartite graphs and load balancing.

[BibT_eX]

[DOI]

Richard E. Ladner

László Lovász

Tami Tamir

J. Algorithms, 2006

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

[BibT_eX]

[DOI]

CoRR, 2006

The complexity of matrix completion.

[BibT_eX]

[DOI]

David R. Karger

Sergey Yekhanin

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

On the capacity of information networks.

[BibT_eX]

[DOI]

Micah Adler

Kamal Jain

Robert D. Kleinberg

April Rasala Lehman

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

Lower bounds for asymmetric communication channels and distributed source coding.

[BibT_eX]

[DOI]

Micah Adler

Erik D. Demaine

Mihai Patrascu

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

Algebraic Structures and Algorithms for Matching and Matroid Problems.

[BibT_eX]

[DOI]

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

2005

Deterministic network coding by matrix completion.

[BibT_eX]

[DOI]

David R. Karger

Kazuo Murota

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

2004

Deterministic SkipNet.

[BibT_eX]

[DOI]

J. Ian Munro

Inf. Process. Lett., 2004

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

[BibT_eX]

[DOI]

Kevin C. Zatloukal

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

FUSE: Lightweight Guaranteed Distributed Failure Notification.

[BibT_eX]

[DOI]

John Dunagan

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

2003

SkipNet: A Scalable Overlay Network with Practical Locality Properties.

[BibT_eX]

[DOI]

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

Brief announcement: deterministic skipnet.

[BibT_eX]

[DOI]

J. Ian Munro

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

Efficient Recovery from Organizational Disconnects in SkipNet.

[BibT_eX]

[DOI]