Robert Krauthgamer

According to our database1, Robert Krauthgamer authored at least 95 papers between 1997 and 2019.

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

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

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

Report on HALG 2018.
Bulletin of the EATCS, 2018

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

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

Local reconstruction of low-rank matrices and subspaces.
Random Struct. Algorithms, 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

Conditional Lower Bounds for All-Pairs Max-Flow.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Minimum Bisection.
Encyclopedia of Algorithms, 2016

Cheeger-Type Approximation for Sparsest st-Cut.
ACM Trans. Algorithms, 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
Local Reconstruction of Low-Rank Matrices and Subspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Sketching and Embedding are Equivalent for Norms.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 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
Preserving Terminal Distances Using Minors.
SIAM J. Discrete Math., 2014

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

Cutting corners cheaply, or how to remove Steiner points.
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
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

Efficient Regression in Metric Spaces via Approximate Lipschitz Extension.
Proceedings of the Similarity-Based Pattern Recognition - Second International Workshop, 2013

Adaptive Metric Dimensionality Reduction.
Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013

2012
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme.
Proceedings of the 44th Symposium on Theory of Computing Conference, 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
Pricing commodities.
Theor. Comput. Sci., 2011

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

A Nonlinear Approach to Dimension Reduction.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

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

Min-max Graph Partitioning and Small Set Expansion.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 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

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

Efficient Classification for Metric Data.
Proceedings of the COLT 2010, 2010

Proximity Algorithms for Nearly-Doubling Spaces.
Proceedings of the Approximation, 2010

Vertex Sparsifiers: New Results from Old Techniques.
Proceedings of the Approximation, 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

How hard is it to approximate the best Nash equilibrium?
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

Metric clustering via consistent labeling.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Earth mover distance over high-dimensional spaces.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

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

The Smoothed Complexity of Edit Distance.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

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 of Computing, 2006

A Polylogarithmic Approximation of the Minimum Bisection.
SIAM Review, 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
Asymmetric k-center is log* n-hard to approximate.
J. ACM, 2005

On the Hardness of Approximating Multicut and Sparsest-Cut.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Metric Embeddings--Beyond One-Dimensional Distortion.
Discrete & Computational Geometry, 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

The Black-Box Complexity of Nearest Neighbor Search.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 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.
Discrete Applied Mathematics, 2003

The intrinsic dimensionality of graphs.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 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

Integrality ratio for group Steiner trees and directed steiner trees.
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

2002
Hardness of Approximation for Vertex-Connectivity Network-Design Problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

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

On approximating the achromatic number.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 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 Computing, 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

A polylogarithmic approximation of the minimum bisection.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

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


  Loading...