Robert Krauthgamer

Discret. Comput. Geom., April, 2024

2023

Comparison of Matrix Norm Sparsification.

[BibT_eX]

[DOI]

Shay Sapir

Algorithmica, December, 2023

Moderate Dimension Reduction for k-Center Clustering.

[BibT_eX]

[DOI]

Shaofeng H.-C. Jiang

Shay Sapir

CoRR, 2023

Cut Sparsification and Succinct Representation of Submodular Hypergraphs.

[BibT_eX]

[DOI]

Yotam Kenneth

CoRR, 2023

Fully Scalable MPC Algorithms for Clustering in High Dimension.

[BibT_eX]

[DOI]

CoRR, 2023

Streaming Euclidean Max-Cut: Dimension vs Data Reduction.

[BibT_eX]

[DOI]

Xiaoyu Chen

Shaofeng H.-C. Jiang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Exact Flow Sparsification Requires Unbounded Size.

[BibT_eX]

[DOI]

Ron Mosenzon

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Clustering Permutations: New Techniques with Streaming Applications.

[BibT_eX]

[DOI]

Diptarka Chakraborty

Debarati Das

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Lower Bounds for Pseudo-Deterministic Counting in a Stream.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Universal Streaming of Subset Norms.

[BibT_eX]

[DOI]

Vladimir Braverman

Lin F. Yang

Theory Comput., 2022

Faster algorithms for orienteering and k-TSP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Smoothness of Schatten norms and sliding-window matrix streams.

[BibT_eX]

[DOI]

Shay Sapir

Inf. Process. Lett., 2022

Streaming Euclidean Max-Cut: Dimension vs Data Reduction.

[BibT_eX]

[DOI]

Yu Chen

Shaofeng H.-C. Jiang

CoRR, 2022

Distributed Sparse Linear Regression with Sublinear Communication.

[BibT_eX]

[DOI]

Chen Amiraz

Boaz Nadler

CoRR, 2022

Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs.

[BibT_eX]

[DOI]

Itai Boneh

CoRR, 2022

Near-Linear ε-Emulators for Planar Graphs.

[BibT_eX]

[DOI]

Hsien-Chih Chang

Zihan Tan

CoRR, 2022

Streaming Facility Location in High Dimension via New Geometric Hashing.

[BibT_eX]

[DOI]

CoRR, 2022

Almost-Smooth Histograms and Sliding-Window Graph Algorithms.

[BibT_eX]

[DOI]

David Reitblat

Algorithmica, 2022

Almost-linear ε-emulators for planar graphs.

[BibT_eX]

[DOI]

Hsien-Chih Chang

Zihan Tan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Streaming Algorithms for Geometric Steiner Forest.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Streaming Facility Location in High Dimension via Geometric Hashing.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

The Power of Uniform Sampling for Coresets.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.

[BibT_eX]

[DOI]

Theory Comput., 2021

Flow Metrics on Graphs.

[BibT_eX]

[DOI]

Lior Kalman

CoRR, 2021

Gomory-Hu Tree in Subcubic Time.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

CoRR, 2021

Coresets for Kernel Clustering.

[BibT_eX]

[DOI]

CoRR, 2021

Sparse Normal Means Estimation with Sublinear Communication.

[BibT_eX]

[DOI]

Chen Amiraz

Boaz Nadler

CoRR, 2021

Towards tight bounds for spectral sparsification of hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Subcubic algorithms for Gomory-Hu tree in unweighted graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Approximating the Median under the Ulam Metric.

[BibT_eX]

[DOI]

Diptarka Chakraborty

Debarati Das

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Coresets for Clustering in Excluded-minor Graphs and Beyond.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Coresets for Clustering with Missing Values.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Approximate Trace Reconstruction via Median String (In Average-Case).

[BibT_eX]

[DOI]

Diptarka Chakraborty

Debarati Das

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Spectral Hypergraph Sparsifiers of Nearly Linear Size.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Refined Vertex Sparsifiers of Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Faster Algorithms for Orienteering and k-TSP.

[BibT_eX]

[DOI]

CoRR, 2020

Labelings vs. Embeddings: On Distributed Representations of Distances.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Coresets for Clustering in Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Sketching Graphs and Combinatorial Optimization (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Cut-Equivalent Trees are Optimal for Min-Cut Queries.

[BibT_eX]

[DOI]

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

2019

Coresets for Clustering in Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

CoRR, 2019

The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Flow-Cut Gaps and Face Covers in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

On Solving Linear Systems in Sublinear Time.

[BibT_eX]

[DOI]

Yosef Pogrow

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Coresets for Ordered Weighted Clustering.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Algorithms for All-Pairs Bounded Min-Cuts.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Sublinear Algorithms for Gap Edit Distance.

[BibT_eX]

[DOI]

Elazar Goldenberg

Barna Saha

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Conditional Lower Bounds for All-Pairs Max-Flow.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

3rd Highlights of Algorithms (HALG 2018).

[BibT_eX]

[DOI]

Artur Czumaj

SIGACT News, 2018

Sketching and Embedding are Equivalent for Norms.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

SIAM J. Comput., 2018

Report on HALG 2018.

[BibT_eX]

[DOI]

Artur Czumaj

Bull. EATCS, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

Efficient Regression in Metric Spaces via Approximate Lipschitz Extension.

[BibT_eX]

[DOI]

Aryeh Kontorovich

IEEE Trans. Inf. Theory, 2017

Sparsification of Two-Variable Valued Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Revisiting the Set Cover Conjecture.

[BibT_eX]

[DOI]

CoRR, 2017

Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern.

[BibT_eX]

[DOI]

CoRR, 2017

Metric Decompositions of Path-Separable Graphs.

[BibT_eX]

[DOI]

Lior Kamma

Algorithmica, 2017

Streaming symmetric norms via measure concentration.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Minimum Bisection.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Adaptive metric dimensionality reduction.

[BibT_eX]

[DOI]

Aryeh Kontorovich

Theor. Comput. Sci., 2016

Cheeger-Type Approximation for Sparsest st-Cut.

[BibT_eX]

[DOI]

Tal Wagner

ACM Trans. Algorithms, 2016

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme.

[BibT_eX]

[DOI]

Yair Bartal

SIAM J. Comput., 2016

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

[BibT_eX]

[DOI]

CoRR, 2016

Tight Bounds for Gomory-Hu-like Cut Counting.

[BibT_eX]

[DOI]

Rajesh Chitnis

Lior Kamma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

On Sketching Quadratic Forms.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Color-Distance Oracles and Snippets.

[BibT_eX]

[DOI]

Tsvi Kopelowitz

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

Cutting Corners Cheaply, or How to Remove Steiner Points.

[BibT_eX]

[DOI]

Lior Kamma

Huy L. Nguyen

SIAM J. Comput., 2015

Local Reconstruction of Low-Rank Matrices and Subspaces.

[BibT_eX]

[DOI]

Roee David

Elazar Goldenberg

Electron. Colloquium Comput. Complex., 2015

A Nonlinear Approach to Dimension Reduction.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2015

Sparsification of Two-Variable Valued CSPs.

[BibT_eX]

[DOI]

CoRR, 2015

Streaming Symmetric Norms via Measure Concentration.

[BibT_eX]

[DOI]

CoRR, 2015

Sketching Cuts in Graphs and Hypergraphs.

[BibT_eX]

[DOI]

Dmitry Kogan

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Towards Resistance Sparsifiers.

[BibT_eX]

[DOI]

Tal Wagner

Proceedings of the Approximation, 2015

Approximate Nearest Neighbor Search in Metrics of Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Efficient Classification for Metric Data.

[BibT_eX]

[DOI]

Aryeh Kontorovich

IEEE Trans. Inf. Theory, 2014

Preserving Terminal Distances Using Minors.

[BibT_eX]

[DOI]

Huy L. Nguyen

Tamar Zondiner

SIAM J. Discret. Math., 2014

Vertex Sparsifiers: New Results from Old Techniques.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Min-Max Graph Partitioning and Small Set Expansion.

[BibT_eX]

[DOI]

Nikhil Bansal

Konstantin Makarychev

Viswanath Nagarajan

Joseph Naor

Roy Schwartz

SIAM J. Comput., 2014

Cheeger-type approximation for sparsest $st$-cut.

[BibT_eX]

[DOI]

Tal Wagner

CoRR, 2014

The Sketching Complexity of Graph Cuts.

[BibT_eX]

[DOI]

David P. Woodruff

CoRR, 2014

Non-Uniform Graph Partitioning.

[BibT_eX]

[DOI]

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

Towards (1 + ∊)-Approximate Flow Sparsifiers.

[BibT_eX]

[DOI]

Anupam Gupta

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

Multiply Balanced k -Partitioning.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Spectral Approaches to Nearest Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Proximity Algorithms for Nearly Doubling Spaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Towards (1+ε)-Approximate Flow Sparsifiers.

[BibT_eX]

[DOI]

Anupam Gupta

CoRR, 2013

Efficient Approximation of Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2013

Mimicking Networks and Succinct Representations of Terminal Cuts.

[BibT_eX]

[DOI]

Inbal Rika

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

The smoothed complexity of edit distance.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Faster Clustering via Preprocessing

[BibT_eX]

[DOI]

Tsvi Kopelowitz

CoRR, 2012

Preserving Terminal Distances Using Minors.

[BibT_eX]

[DOI]

Tamar Zondiner

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Everywhere-Sparse Spanners via Dense Subgraphs.

[BibT_eX]

[DOI]

Eden Chlamtac

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Metric Clustering via Consistent Labeling.

[BibT_eX]

[DOI]

Tim Roughgarden

Theory Comput., 2011

Pricing commodities.

[BibT_eX]

[DOI]

Aranyak Mehta

Atri Rudra

Theor. Comput. Sci., 2011

How Hard Is It to Approximate the Best Nash Equilibrium?

[BibT_eX]

[DOI]

Elad Hazan

SIAM J. Comput., 2011

Directed spanners via flow-based linear programs.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Fault-tolerant spanners: better and simpler.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Streaming Algorithms via Precision Sampling.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

The Computational Hardness of Estimating Edit Distance.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Streaming Algorithms from Precision Sampling

[BibT_eX]

[DOI]

CoRR, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Approximating Sparsest Cut in Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Eden Chlamtac

Prasad Raghavendra

Proceedings of the Approximation, 2010

2009

Improved Lower Bounds for Embeddings intoL1$.

[BibT_eX]

[DOI]

Yuval Rabani

SIAM J. Comput., 2009

Partitioning graphs into balanced components.

[BibT_eX]

[DOI]

Joseph Naor

Roy Schwartz

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

Approximate line nearest neighbor in high dimensions.

[BibT_eX]

[DOI]

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

Overcoming the l1 non-embeddability barrier: algorithms for product metrics.

[BibT_eX]

[DOI]

Piotr Indyk

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

2008

Minimum Bisection.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Greedy List Intersection.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Data Engineering, 2008

2007

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Earth Mover Distance over High-Dimensional Spaces.

[BibT_eX]

[DOI]

Piotr Indyk

Electron. Colloquium Comput. Complex., 2007

The intrinsic dimensionality of graphs.

[BibT_eX]

[DOI]

Comb., 2007

Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations.

[BibT_eX]

[DOI]

Aranyak Mehta

Atri Rudra

Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

On triangulation of simple networks.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

The Computational Hardness of Estimating Edit Distance [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Embedding the Ulam metric into l1.

[BibT_eX]

[DOI]

Moses Charikar

Theory Comput., 2006

A Polylogarithmic Approximation of the Minimum Bisection.

[BibT_eX]

[DOI]

SIAM Rev., 2006

On the Hardness of Approximating Multicut and Sparsest-Cut.

[BibT_eX]

[DOI]

Comput. Complex., 2006

Improved lower bounds for embeddings into L1.

[BibT_eX]

[DOI]

Yuval Rabani

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

Algorithms on negatively curved spaces.

[BibT_eX]

[DOI]

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

2005

The black-box complexity of nearest-neighbor search.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Asymmetric k-center is log* n-hard to approximate.

[BibT_eX]

[DOI]

J. ACM, 2005

2004

Hardness of Approximation for Vertex-Connectivity Network Design Problems.

[BibT_eX]

[DOI]

Guy Kortsarz

SIAM J. Comput., 2004

Metric Embeddings--Beyond One-Dimensional Distortion.

[BibT_eX]

[DOI]

Nathan Linial

Avner Magen

Discret. Comput. Geom., 2004

Object location in realistic networks.

[BibT_eX]

[DOI]

Kirsten Hildrum

John Kubiatowicz

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.

[BibT_eX]

[DOI]

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

Approximate classification via earthmover metrics.

[BibT_eX]

[DOI]

Aaron Archer

Jittat Fakcharoenphol

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

Measured Descent: A New Embedding Method for Finite Metrics.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Approximating Edit Distance Efficiently.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

The Sketching Complexity of Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Tight lower bounds for the asymmetric k-center problem

[BibT_eX]

[DOI]

Eran Halperin

Guy Kortsarz

Electron. Colloquium Comput. Complex., 2003

On Cutting a Few Vertices from a Graph.

[BibT_eX]

[DOI]

Kobbi Nissim

Discret. Appl. Math., 2003

Polylogarithmic inapproximability.

[BibT_eX]

[DOI]

Eran Halperin

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

Constant factor approximation of vertex-cuts in planar graphs.

[BibT_eX]

[DOI]

Eyal Amir

Satish Rao

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

Property testing of data dimensionality.

[BibT_eX]

[DOI]

Ori Sasson

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Detecting protein sequence conservation via metric embeddings.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Bounded Geometries, Fractals, and Low-Distortion Embeddings.

[BibT_eX]

[DOI]

Anupam Gupta

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

On Approximating the Achromatic Number.

[BibT_eX]

[DOI]

Guy Kortsarz

SIAM J. Discret. Math., 2001

Online server allocation in a server farm via benefit task systems.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Private approximation of NP-hard functions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2000

Networks on Which Hot-Potato Routing Does Not Livelock.

[BibT_eX]

[DOI]

Distributed Comput., 2000

Approximating the minimum bisection size (extended abstract).

[BibT_eX]

[DOI]

Kobbi Nissim

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Improved classification via connectivity information.

[BibT_eX]

[DOI]

Andrei Z. Broder

Michael Mitzenmacher

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1997

Stereoscopic families of permutations, and their applications.

[BibT_eX]

[DOI]