Robert Krauthgamer

According to our database1, Robert Krauthgamer authored at least 120 papers between 1997 and 2020.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2020
Refined Vertex Sparsifiers of Planar Graphs.
SIAM J. Discret. Math., 2020

Coresets for Clustering in Excluded-minor Graphs and Beyond.
CoRR, 2020

Faster Algorithms for Orienteering and k-TSP.
CoRR, 2020

Labelings vs. Embeddings: On Distributed Representations of Distances.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Sketching Graphs and Combinatorial Optimization (Invited Talk).
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension.
CoRR, 2019

Coresets for Clustering in Graphs of Bounded Treewidth.
CoRR, 2019

Almost-Smooth Histograms and Sliding-Window Graph Algorithms.
CoRR, 2019

The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Flow-Cut Gaps and Face Covers in Planar Graphs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

On Solving Linear Systems in Sublinear Time.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Coresets for Ordered Weighted Clustering.
Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Algorithms for All-Pairs Bounded Min-Cuts.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Sublinear Algorithms for Gap Edit Distance.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Conditional Lower Bounds for All-Pairs Max-Flow.
ACM Trans. Algorithms, 2018

3rd Highlights of Algorithms (HALG 2018).
SIGACT News, 2018

Sketching and Embedding are Equivalent for Norms.
SIAM J. Comput., 2018

Report on HALG 2018.
Bull. EATCS, 2018

Universal Streaming of Subset Norms.
CoRR, 2018

Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems.
CoRR, 2018

Batch Sparse Recovery, or How to Leverage the Average Sparsity.
CoRR, 2018

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.
Proceedings of the 35th International Conference on Machine Learning, 2018

2017
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension.
IEEE Trans. Inf. Theory, 2017

Sparsification of Two-Variable Valued Constraint Satisfaction Problems.
SIAM J. Discret. Math., 2017

Revisiting the Set Cover Conjecture.
CoRR, 2017

Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern.
CoRR, 2017

Metric Decompositions of Path-Separable Graphs.
Algorithmica, 2017

Streaming symmetric norms via measure concentration.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016
Minimum Bisection.
Encyclopedia of Algorithms, 2016

Adaptive metric dimensionality reduction.
Theor. Comput. Sci., 2016

Cheeger-Type Approximation for Sparsest st-Cut.
ACM Trans. Algorithms, 2016

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme.
SIAM J. Comput., 2016

Sketches for Matrix Norms: Faster, Smaller and More General.
CoRR, 2016

Tight Bounds for Gomory-Hu-like Cut Counting.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

On Sketching Quadratic Forms.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Color-Distance Oracles and Snippets.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015
Cutting Corners Cheaply, or How to Remove Steiner Points.
SIAM J. Comput., 2015

Local Reconstruction of Low-Rank Matrices and Subspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2015

A Nonlinear Approach to Dimension Reduction.
Discret. Comput. Geom., 2015

Sparsification of Two-Variable Valued CSPs.
CoRR, 2015

Streaming Symmetric Norms via Measure Concentration.
CoRR, 2015

Sketching Cuts in Graphs and Hypergraphs.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Towards Resistance Sparsifiers.
Proceedings of the Approximation, 2015

Approximate Nearest Neighbor Search in Metrics of Planar Graphs.
Proceedings of the Approximation, 2015

2014
Efficient Classification for Metric Data.
IEEE Trans. Inf. Theory, 2014

Preserving Terminal Distances Using Minors.
SIAM J. Discret. Math., 2014

Vertex Sparsifiers: New Results from Old Techniques.
SIAM J. Comput., 2014

Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 2014

Cheeger-type approximation for sparsest $st$-cut.
CoRR, 2014

The Sketching Complexity of Graph Cuts.
CoRR, 2014

Non-Uniform Graph Partitioning.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Towards (1 + )-Approximate Flow Sparsifiers.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multiply Balanced k -Partitioning.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Orienting Fully Dynamic Graphs with Worst-Case Time Bounds.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Spectral Approaches to Nearest Neighbor Search.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Proximity Algorithms for Nearly Doubling Spaces.
SIAM J. Discret. Math., 2013

Towards (1+ε)-Approximate Flow Sparsifiers.
CoRR, 2013

Efficient Approximation of Edit Distance.
Proceedings of the String Processing and Information Retrieval, 2013

Mimicking Networks and Succinct Representations of Terminal Cuts.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
The smoothed complexity of edit distance.
ACM Trans. Algorithms, 2012

Faster Clustering via Preprocessing
CoRR, 2012

Preserving Terminal Distances Using Minors.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Everywhere-Sparse Spanners via Dense Subgraphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Metric Clustering via Consistent Labeling.
Theory Comput., 2011

Pricing commodities.
Theor. Comput. Sci., 2011

How Hard Is It to Approximate the Best Nash Equilibrium?
SIAM J. Comput., 2011

Directed spanners via flow-based linear programs.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Fault-tolerant spanners: better and simpler.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Streaming Algorithms via Precision Sampling.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
The Computational Hardness of Estimating Edit Distance.
SIAM J. Comput., 2010

Streaming Algorithms from Precision Sampling
CoRR, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Approximating Sparsest Cut in Graphs of Bounded Treewidth.
Proceedings of the Approximation, 2010

2009
Improved Lower Bounds for Embeddings intoL1$.
SIAM J. Comput., 2009

Partitioning graphs into balanced components.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximate line nearest neighbor in high dimensions.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Overcoming the l1 non-embeddability barrier: algorithms for product metrics.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Minimum Bisection.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Greedy List Intersection.
Proceedings of the 24th International Conference on Data Engineering, 2008

2007
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees.
SIAM J. Comput., 2007

Earth Mover Distance over High-Dimensional Spaces.
Electronic Colloquium on Computational Complexity (ECCC), 2007

The intrinsic dimensionality of graphs.
Combinatorica, 2007

Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

On triangulation of simple networks.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Estimating the sortedness of a data stream.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The Computational Hardness of Estimating Edit Distance [Extended Abstract].
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006
Embedding the Ulam metric into l1.
Theory Comput., 2006

A Polylogarithmic Approximation of the Minimum Bisection.
SIAM Review, 2006

On the Hardness of Approximating Multicut and Sparsest-Cut.
Comput. Complex., 2006

Improved lower bounds for embeddings into L1.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Algorithms on negatively curved spaces.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
The black-box complexity of nearest-neighbor search.
Theor. Comput. Sci., 2005

Asymmetric k-center is log* n-hard to approximate.
J. ACM, 2005

2004
Hardness of Approximation for Vertex-Connectivity Network Design Problems.
SIAM J. Comput., 2004

Metric Embeddings--Beyond One-Dimensional Distortion.
Discret. Comput. Geom., 2004

Object location in realistic networks.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Navigating nets: simple algorithms for proximity search.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Approximate classification via earthmover metrics.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Measured Descent: A New Embedding Method for Finite Metrics.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Approximating Edit Distance Efficiently.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

The Sketching Complexity of Pattern Matching.
Proceedings of the Approximation, 2004

2003
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.
SIAM J. Comput., 2003

Tight lower bounds for the asymmetric k-center problem
Electronic Colloquium on Computational Complexity (ECCC), 2003

On Cutting a Few Vertices from a Graph.
Discret. Appl. Math., 2003

Polylogarithmic inapproximability.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Constant factor approximation of vertex-cuts in planar graphs.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Property testing of data dimensionality.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Detecting protein sequence conservation via metric embeddings.
Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Bounded Geometries, Fractals, and Low-Distortion Embeddings.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001
On Approximating the Achromatic Number.
SIAM J. Discret. Math., 2001

Online server allocation in a server farm via benefit task systems.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Private approximation of NP-hard functions.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms, 2000

Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Comput., 2000

Approximating the minimum bisection size (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Improved classification via connectivity information.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1997
Stereoscopic families of permutations, and their applications.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997


  Loading...