We stand with Ukraine

We stand with Ukraine

Sanjeev Khanna

Orcid: 0009-0000-2601-1689

Affiliations:

University of Pennsylvania, Philadelphia, PA, USA

According to our database¹, Sanjeev Khanna authored at least 227 papers between 1990 and 2025.

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of two.

Awards

ACM Fellow

ACM Fellow 2018, "For contributions to approximation algorithms, hardness of approximation, and sublinear algorithms".

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

Online presence:

On csauthors.net:

Bibliography

2025

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs.

[BibT_eX]

[DOI]

,

,

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

2024

Improved Approximation Algorithms for Flexible Graph Connectivity and Capacitated Network Design.

[BibT_eX]

[DOI]

,

Joseph Cheriyan

,

,

CoRR, 2024

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs.

[BibT_eX]

[DOI]

,

CoRR, 2024

Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs.

[BibT_eX]

[DOI]

,

Aaron (Louie) Putterman

,

CoRR, 2024

Maximum Bipartite Matching in n<sup>2+o(1)</sup> Time via a Combinatorial Algorithm.

[BibT_eX]

[DOI]

,

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Code Sparsification and its Applications.

[BibT_eX]

[DOI]

,

Aaron (Louie) Putterman

,

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

A Faster Combinatorial Algorithm for Maximum Bipartite Matching.

[BibT_eX]

[DOI]

,

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

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth.

[BibT_eX]

[DOI]

,

,

,

Prathamesh Patil

,

,

,

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

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs.

[BibT_eX]

[DOI]

,

Aaron (Louie) Putterman

,

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers.

[BibT_eX]

[DOI]

,

Aaron Putterman

,

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

On Regularity Lemma and Barriers in Streaming and Dynamic Matching.

[BibT_eX]

[DOI]

,

Soheil Behnezhad

,

,

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

Query Complexity of the Metric Steiner Tree Problem.

[BibT_eX]

[DOI]

,

,

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

Set Cover in the One-pass Edge-arrival Streaming Model.

[BibT_eX]

[DOI]

,

Christian Konrad

,

Cezar-Mihail Alexandru

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics.

[BibT_eX]

[DOI]

,

,

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

2022

Nearly Tight Bounds for Discrete Search under Outlier Noise.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS.

[BibT_eX]

[DOI]

Soheil Behnezhad

,

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

Sublinear Algorithms for Hierarchical Clustering.

[BibT_eX]

[DOI]

,

,

,

Prathamesh Patil

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Optimal Bounds for Dominating Set in Graph Streams.

[BibT_eX]

[DOI]

,

Christian Konrad

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

On Weighted Graph Sparsification by Linear Sketching.

[BibT_eX]

[DOI]

,

,

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

A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits.

[BibT_eX]

[DOI]

,

,

Prathamesh Patil

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

PAC Top-k Identification under SST in Limited Rounds.

[BibT_eX]

[DOI]

,

,

Prathamesh Patil

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem.

[BibT_eX]

[DOI]

,

,

SIAM J. Comput., 2021

Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

Math. Program., 2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

,

CoRR, 2021

Hardness of Approximation for Orienteering with Multiple Time Windows.

[BibT_eX]

[DOI]

,

,

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

Approximate optimization of convex functions with outlier noise.

[BibT_eX]

[DOI]

,

,

,

MohammadHesam NikpeySalekde

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

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries.

[BibT_eX]

[DOI]

,

,

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

,

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

Graph Connectivity and Single Element Recovery via Linear and OR Queries.

[BibT_eX]

[DOI]

,

Deeparnab Chakrabarty

,

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs.

[BibT_eX]

[DOI]

Mudabir Kabir Asathulla

,

,

,

Sharath Raghvendra

ACM Trans. Algorithms, 2020

Near-Perfect Recovery in the One-Dimensional Latent Space Model.

[BibT_eX]

[DOI]

,

,

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Space-efficient Query Evaluation over Probabilistic Event Streams.

[BibT_eX]

[DOI]

,

,

Kishor Jothimurugan

,

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions.

[BibT_eX]

[DOI]

,

Shivani Agarwal

,

,

Prathamesh Patil

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

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs.

[BibT_eX]

[DOI]

,

,

,

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

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation.

[BibT_eX]

[DOI]

,

,

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

Near-linear Size Hypergraph Cut Sparsifiers.

[BibT_eX]

[DOI]

,

,

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

2019

The Stochastic Matching Problem with (Very) Few Queries.

[BibT_eX]

[DOI]

,

,

ACM Trans. Economics and Comput., 2019

Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

Comb., 2019

A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.

[BibT_eX]

[DOI]

,

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Polynomial pass lower bounds for graph streaming algorithms.

[BibT_eX]

[DOI]

,

,

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sublinear Algorithms for (Δ + 1) Vertex Coloring.

[BibT_eX]

[DOI]

,

,

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

Stochastic Submodular Cover with Limited Adaptivity.

[BibT_eX]

[DOI]

,

,

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

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

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

Network Formation under Random Attack and Probabilistic Spread.

[BibT_eX]

[DOI]

,

,

Michael J. Kearns

,

,

Jamie Morgenstern

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

2018

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.

[BibT_eX]

[DOI]

,

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

Testing Graph Clusterability: Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

Ashish Chiplunkar

,

Michael Kapralov

,

,

Aida Mousavifar

,

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Fast Convergence in the Double Oral Auction.

[BibT_eX]

[DOI]

,

,

,

ACM Trans. Economics and Comput., 2017

A greedy approximation algorithm for minimum-gap scheduling.

[BibT_eX]

[DOI]

,

,

Mohammad Taghi Hajiaghayi

,

,

,

J. Sched., 2017

Randomized Composable Coresets for Matching and Vertex Cover.

[BibT_eX]

[DOI]

,

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.

[BibT_eX]

[DOI]

Michael Kapralov

,

,

,

Ameya Velingker

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On Estimating Maximum Matching Size in Graph Streams.

[BibT_eX]

[DOI]

,

,

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm.

[BibT_eX]

[DOI]

,

,

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data.

[BibT_eX]

[DOI]

Konstantinos Mamouras

,

Mukund Raghothaman

,

,

Zachary G. Ives

,

Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2017

Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.

[BibT_eX]

[DOI]

,

Shivani Agarwal

,

,

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Effective and efficient similarity search in scientific workflow repositories.

[BibT_eX]

[DOI]

Johannes Starlinger

,

Sarah Cohen Boulakia

,

,

Susan B. Davidson

,

Future Gener. Comput. Syst., 2016

Sensitivity and computational complexity in financial networks.

[BibT_eX]

[DOI]

,

Algorithmic Finance, 2016

Strategic Network Formation with Attack and Immunization.

[BibT_eX]

[DOI]

,

,

Michael J. Kearns

,

,

Jamie Morgenstern

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.

[BibT_eX]

[DOI]

,

,

,

Grigory Yaroslavtsev

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Rapid convergence versus policy expressiveness in interdomain routing.

[BibT_eX]

[DOI]

Alexander J. T. Gurney

,

,

Proceedings of the 35th Annual IEEE International Conference on Computer Communications, 2016

Algorithms for Provisioning Queries and Analytics.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 19th International Conference on Database Theory, 2016

Quantiles and Equi-depth Histograms over Streams.

[BibT_eX]

[DOI]

Michael B. Greenwald

,

Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015

On the Power of Planned Infections in Networks.

[BibT_eX]

[DOI]

Michael Brautbar

,

,

Internet Math., 2015

Tight Bounds for Linear Sketches of Approximate Matchings.

[BibT_eX]

[DOI]

,

,

,

Grigory Yaroslavtsev

CoRR, 2015

Approximability of Capacitated Network Design.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

Chandra Chekuri

,

,

Algorithmica, 2015

Streaming Lower Bounds for Approximating MAX-CUT.

[BibT_eX]

[DOI]

Michael Kapralov

,

,

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Connectivity in Random Forests and Credit Networks.

[BibT_eX]

[DOI]

,

,

Sharath Raghvendra

,

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On (1, <i>∊</i>)-Restricted Assignment Makespan Minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

,

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On embeddability of modular robot designs.

[BibT_eX]

[DOI]

Yannis Mantzouratos

,

,

,

Proceedings of the IEEE International Conference on Robotics and Automation, 2015

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Top-k and Clustering with Noisy Comparisons.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

,

ACM Trans. Database Syst., 2014

On $(1, ε)$-Restricted Assignment Makespan Minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

,

CoRR, 2014

Influence Maximization in Undirected Networks.

[BibT_eX]

[DOI]

,

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

Approximating matching size from random streams.

[BibT_eX]

[DOI]

Michael Kapralov

,

,

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

Disjoint Set Union with Randomized Linking.

[BibT_eX]

[DOI]

,

,

Daniel H. Larkin

,

Robert Endre Tarjan

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

Fast and Improved SLEX Analysis of High-Dimensional Time Series.

[BibT_eX]

[DOI]

,

,

,

Matthew A. Smith

,

Geoffrey J. Gordon

Proceedings of the Machine Learning and Interpretation in Neuroimaging, 2014

Matchings, Random Walks, and Sampling.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2014

A Utility Equivalence Theorem for Concave Functions.

[BibT_eX]

[DOI]

,

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Layer Decomposition: An Effective Structure-Based Approach for Scientific Workflow Similarity.

[BibT_eX]

[DOI]

Johannes Starlinger

,

Sarah Cohen Boulakia

,

,

Susan B. Davidson

,

Proceedings of the 10th IEEE International Conference on e-Science, 2014

Differential Privacy: An Economic Method for Choosing Epsilon.

[BibT_eX]

[DOI]

,

,

Andreas Haeberlen

,

,

,

Benjamin C. Pierce

,

Proceedings of the IEEE 27th Computer Security Foundations Symposium, 2014

2013

Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

SIAM J. Comput., 2013

The All-or-Nothing Multicommodity Flow Problem.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

SIAM J. Comput., 2013

Dynamic and Nonuniform Pricing Strategies for Revenue Maximization.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

,

,

SIAM J. Comput., 2013

On the Power of Adversarial Infections in Networks.

[BibT_eX]

[DOI]

Michael Brautbar

,

,

Proceedings of the Algorithms and Models for the Web Graph - 10th International Workshop, 2013

Using the crowd for top-k and group-by queries.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

,

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

To Show or Not to Show in Workflow Provenance.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

Proceedings of the In Search of Elegance in the Theory and Practice of Computation, 2013

2012

Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks.

[BibT_eX]

[DOI]

,

Santosh S. Venkatesh

,

,

,

IEEE/ACM Trans. Netw., 2012

An O(k<sup>3</sup>log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.

[BibT_eX]

[DOI]

,

Theory Comput., 2012

The Power of Local Information in Social Networks.

[BibT_eX]

[DOI]

Christian Borgs

,

Michael Brautbar

,

Jennifer T. Chayes

,

,

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Mechanism Design for a Risk Averse Seller.

[BibT_eX]

[DOI]

,

Tanmoy Chakraborty

,

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

On the communication and streaming complexity of maximum bipartite matching.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Distributed Private Heavy Hitters.

[BibT_eX]

[DOI]

,

,

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

Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.

[BibT_eX]

[DOI]

Parinya Chalermsook

,

,

,

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Queries with Difference on Probabilistic Databases.

[BibT_eX]

[DOI]

,

,

Proc. VLDB Endow., 2011

Mechanism Design with Risk Aversion

[BibT_eX]

[DOI]

,

Tanmoy Chakraborty

,

CoRR, 2011

Improved Approximation Results for Stochastic Knapsack Problems.

[BibT_eX]

[DOI]

,

,

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Provenance views for module privacy.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

,

Debmalya Panigrahi

,

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Compression without a common prior: an information-theoretic justification for ambiguity in language.

[BibT_eX]

[DOI]

,

Adam Tauman Kalai

,

,

Proceedings of the Innovations in Computer Science, 2011

On provenance and privacy.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

,

Julia Stoyanovich

,

,

Proceedings of the Database Theory, 2011

Delays and the Capacity of Continuous-Time Channels.

[BibT_eX]

[DOI]

,

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

Algorithms for the Generalized Sorting Problem.

[BibT_eX]

[DOI]

,

,

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

Enabling Privacy in Provenance-Aware Workflow Systems.

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

,

,

,

,

Julia Stoyanovich

Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research, 2011

Social Welfare in One-Sided Matching Markets without Money.

[BibT_eX]

[DOI]

,

Deeparnab Chakrabarty

,

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.

[BibT_eX]

[DOI]

,

Deeparnab Chakrabarty

,

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Perfect matchings via uniform sampling in regular bipartite graphs.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

ACM Trans. Algorithms, 2010

Robust self-assembly of graphs.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

Mirkó Visontai

Nat. Comput., 2010

Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP

[BibT_eX]

[DOI]

,

Deeparnab Chakrabarty

,

CoRR, 2010

Preserving Module Privacy in Workflow Provenance

[BibT_eX]

[DOI]

Susan B. Davidson

,

,

Debmalya Panigrahi

,

CoRR, 2010

Graph Sparsification via Refinement Sampling

[BibT_eX]

[DOI]

,

Michael Kapralov

,

CoRR, 2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.

[BibT_eX]

[DOI]

,

Parinya Chalermsook

,

,

Bundit Laekhanukit

,

Danupon Nanongkai

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Perfect matchings in o(<i>n</i> log <i>n</i>) time in regular bipartite graphs.

[BibT_eX]

[DOI]

,

Michael Kapralov

,

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

An optimal labeling scheme for workflow provenance using skeleton labels.

[BibT_eX]

[DOI]

,

Susan B. Davidson

,

,

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010

Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games.

[BibT_eX]

[DOI]

,

Tanmoy Chakraborty

,

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

Dynamic and non-uniform pricing strategies for revenue maximization.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

,

,

Proceedings of the Behavioral and Quantitative Game Theory, 2010

2009

Approximation algorithms for data placement on parallel disks.

[BibT_eX]

[DOI]

Leana Golubchik

,

,

,

Ramakrishna Thurimella

,

ACM Trans. Algorithms, 2009

Edge-Disjoint Paths in Planar Graphs with Constant Congestion.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

SIAM J. Comput., 2009

Polynomial flow-cut gaps and hardness of directed cut problems.

[BibT_eX]

[DOI]

,

J. ACM, 2009

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing

[BibT_eX]

[DOI]

,

CoRR, 2009

Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs

[BibT_eX]

[DOI]

,

Michael Kapralov

,

CoRR, 2009

Perfect Matchings in Õ(n<sup>1.5</sup>) Time in Regular Bipartite Graphs

[BibT_eX]

[DOI]

,

CoRR, 2009

A Note on Multiflows and Treewidth.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

Algorithmica, 2009

The Network as a Storage Device: Dynamic Routing with Bounded Buffers.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

Algorithmica, 2009

Nash Dynamics in Congestion Games with Similar Resources.

[BibT_eX]

[DOI]

,

Tanmoy Chakraborty

,

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

The ratio index for budgeted learning, with applications.

[BibT_eX]

[DOI]

,

,

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

Network bargaining: algorithms and structural results.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

,

Michael J. Kearns

,

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Automatic construction of a minimum size motion graph.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2009

Nash Dynamics in Constant Player and Bounded Jump Congestion Games.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

,

Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

Optimizing user views for workflows.

[BibT_eX]

[DOI]

,

Susan B. Davidson

,

,

Proceedings of the Database Theory, 2009

Differencing Provenance in Scientific Workflows.

[BibT_eX]

[DOI]

,

Sarah Cohen Boulakia

,

Susan B. Davidson

,

,

Proceedings of the 25th International Conference on Data Engineering, 2009

An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.

[BibT_eX]

[DOI]

,

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On Allocating Goods to Maximize Fairness.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

,

,

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

On the complexity of graph self-assembly in accretive systems.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

Mirkó Visontai

Nat. Comput., 2008

Network design for vertex connectivity.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

,

,

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

On the Network Coding Advantage for Wireless Multicast in Euclidean Space.

[BibT_eX]

[DOI]

,

Proceedings of the 7th International Conference on Information Processing in Sensor Networks, 2008

Adaptive SelectiveVerification.

[BibT_eX]

[DOI]

,

Santosh S. Venkatesh

,

,

,

Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

Algorithms for 2-Route Cut Problems.

[BibT_eX]

[DOI]

Chandra Chekuri

,

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

STCON in Directed Unique-Path Graphs.

[BibT_eX]

[DOI]

,

,

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Algorithms for Single-Source Vertex Connectivity.

[BibT_eX]

[DOI]

,

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

2007

Edge-disjoint paths revisited.

[BibT_eX]

[DOI]

Chandra Chekuri

,

ACM Trans. Algorithms, 2007

Efficient Enumeration of Phylogenetically Informative Substrings.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

,

,

J. Comput. Biol., 2007

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.

[BibT_eX]

[DOI]

Matthew Andrews

,

,

Venkatesan Guruswami

,

,

,

Electron. Colloquium Comput. Complex., 2007

Hardness of routing with congestion in directed graphs.

[BibT_eX]

[DOI]

,

Venkatesan Guruswami

,

,

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

A Formal Investigation of.

[BibT_eX]

[DOI]

,

,

Benjamin C. Pierce

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006

An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

Theory Comput., 2006

Randomized Pursuit-Evasion with Local Visibility.

[BibT_eX]

[DOI]

,

,

SIAM J. Discret. Math., 2006

Hardness of Directed Routing with Congestion.

[BibT_eX]

[DOI]

,

Electron. Colloquium Comput. Complex., 2006

Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data.

[BibT_eX]

[DOI]

Michael B. Greenwald

,

,

,

Benjamin C. Pierce

,

Proceedings of the Distributed Computing, 20th International Symposium, 2006

Hardness of cut problems in directed graphs.

[BibT_eX]

[DOI]

,

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

Randomized pursuit-evasion in a polygonal environment.

[BibT_eX]

[DOI]

,

,

IEEE Trans. Robotics, 2005

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem.

[BibT_eX]

[DOI]

Chandra Chekuri

,

SIAM J. Comput., 2005

Asymmetric <i>k</i>-center is log<sup>*</sup> <i>n</i>-hard to approximate.

[BibT_eX]

[DOI]

,

,

,

,

,

Robert Krauthgamer

,

J. ACM, 2005

Target tracking with distributed sensors: The focus of attention problem.

[BibT_eX]

[DOI]

,

,

John R. Spletzer

,

Camillo J. Taylor

Comput. Vis. Image Underst., 2005

Multicommodity flow, well-linked terminals, and routing problems.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximating the average response time in broadcast scheduling.

[BibT_eX]

[DOI]

,

,

,

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

Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.

[BibT_eX]

[DOI]

Matthew Andrews

,

,

,

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Approximation Algorithms for Minimizing AverageWeighted Completion Time.

[BibT_eX]

[DOI]

Chandra Chekuri

,

Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

Archiving scientific data.

[BibT_eX]

[DOI]

,

,

,

ACM Trans. Database Syst., 2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

,

SIAM J. Discret. Math., 2004

On Multidimensional Packing Problems.

[BibT_eX]

[DOI]

Chandra Chekuri

,

SIAM J. Comput., 2004

Special issue: 35th Annual ACM Symposium on Theory of Computing.

[BibT_eX]

[DOI]

,

Aravind Srinivasan

J. Comput. Syst. Sci., 2004

Locating and Capturing an Evader in a Polygonal Environment.

[BibT_eX]

[DOI]

,

,

Proceedings of the Algorithmic Foundations of Robotics VI, 2004

ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

,

Fernando Pereira

Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Genome Identification and Classification by Short Oligo Arrays.

[BibT_eX]

[DOI]

Stanislav Angelov

,

,

,

,

,

Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Asymmetric k-center is log<sup>*</sup> <i>n</i>-hard to approximate.

[BibT_eX]

[DOI]

,

,

,

,

,

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multi-processor scheduling to minimize flow time with epsilon resource augmentation.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

,

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Randomized pursuit-evasion with limited visibility.

[BibT_eX]

[DOI]

,

,

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

Reconstructing strings from random traces.

[BibT_eX]

[DOI]

,

,

,

Andrew McGregor

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

Power-Conserving Computation of Order-Statistics over Sensor Networks.

[BibT_eX]

[DOI]

Michael Greenwald

,

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

DoS Protection for Reliably Authenticated Broadcast.

[BibT_eX]

[DOI]

,

,

,

Santosh S. Venkatesh

Proceedings of the Network and Distributed System Security Symposium, 2004

Approximating Longest Directed Paths and Cycles.

[BibT_eX]

[DOI]

Andreas Björklund

,

,

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Machine Minimization for Scheduling Jobs with Interval Constraints.

[BibT_eX]

[DOI]

,

,

,

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

Edge-Disjoint Paths in Planar Graphs.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

F. Bruce Shepherd

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

2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.

[BibT_eX]

[DOI]

Venkatesan Guruswami

,

,

Rajmohan Rajaraman

,

F. Bruce Shepherd

,

Mihalis Yannakakis

J. Comput. Syst. Sci., 2003

Asymmetric k-center is log<sup>*</sup>n-hard to Approximate

[BibT_eX]

[DOI]

,

,

,

Electron. Colloquium Comput. Complex., 2003

Approximating Longest Directed Path

[BibT_eX]

[DOI]

Andreas Björklund

,

,

Electron. Colloquium Comput. Complex., 2003

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.

[BibT_eX]

[DOI]

,

,

Rajmohan Rajaraman

,

Algorithmica, 2003

Selection with monotone comparison cost.

[BibT_eX]

[DOI]

,

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

2002

Guest Editor's Foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

On Propagation of Deletions and Annotations Through Views.

[BibT_eX]

[DOI]

,

,

Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

Control Message Aggregation in Group Communication Protocols.

[BibT_eX]

[DOI]

,

,

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

Approximation Schemes for Preemptive Weighted Flow Time

[BibT_eX]

[DOI]

Chandra Chekuri

,

Electron. Colloquium Comput. Complex., 2001

Algorithms for minimizing weighted flow time.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

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

Approximation algorithms for the metric labeling problem via a new linear programming formulation.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

,

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A deterministic algorithm for the cost-distance problem.

[BibT_eX]

[DOI]

Chandra Chekuri

,

,

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Space-Efficient Online Computation of Quantile Summaries.

[BibT_eX]

[DOI]

Michael Greenwald

,

Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001

Fair Real-Time Traffic Scheduling over a Wireless LA.

[BibT_eX]

[DOI]

,

,

,

,

Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), 2001

On Computing Functions with Uncertainty.

[BibT_eX]

[DOI]

,

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Why and Where: A Characterization of Data Provenance.

[BibT_eX]

[DOI]

,

,

Proceedings of the Database Theory, 2001

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.

[BibT_eX]

[DOI]

Chandra Chekuri

,

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Complexity classifications of Boolean constraint satisfaction problems.

[BibT_eX]

,

,

SIAM monographs on discrete mathematics and applications 7, SIAM, ISBN: 978-0-89871-479-1, 2001

2000

The Approximability of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

,

,

,

David P. Williamson

SIAM J. Comput., 2000

On Broadcast Disk Paging.

[BibT_eX]

[DOI]

,

Vincenzo Liberatore

SIAM J. Comput., 2000

On Indexed Data Broadcast

[BibT_eX]

[DOI]

,

J. Comput. Syst. Sci., 2000

On the Hardness of 4-coloring a 3-colorable Graph

[BibT_eX]

[DOI]

Venkatesan Guruswami

,

Electron. Colloquium Comput. Complex., 2000

On the Hardness of Approximating the Chromatic Number.

[BibT_eX]

[DOI]

,

,

Comb., 2000

Watermarking maps: hiding information in structured data.

[BibT_eX]

[DOI]

,

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

Directed network design with orientation constraints.

[BibT_eX]

[DOI]

,

,

F. Bruce Shepherd

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

A PTAS for the multiple knapsack problem.

[BibT_eX]

[DOI]

Chandra Chekuri

,

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

Data Provenance: Some Basic Issues.

[BibT_eX]

[DOI]

,

,

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999

The Angular-Metric Traveling Salesman Problem.

[BibT_eX]

[DOI]

,

Don Coppersmith

,

,

,

Baruch Schieber

SIAM J. Comput., 1999

Design Networks with Bounded Pairwise Distance.

[BibT_eX]

[DOI]

,

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The 2-Catalog Segmentation Problem.

[BibT_eX]

[DOI]

,

Venkatesan Guruswami

,

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On Multi-Dimensional Packing Problems.

[BibT_eX]

[DOI]

Chandra Chekuri

,

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Page Replacement for General Caching Problems.

[BibT_eX]

[DOI]

,

,

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch.

[BibT_eX]

[DOI]

Matthew Andrews

,

,

Krishnan Kumaran

Proceedings of the Proceedings IEEE INFOCOM '99, 1999

Space Time Tradeoffs for Graph Properties.

[BibT_eX]

[DOI]

,

Proceedings of the Automata, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.

[BibT_eX]

[DOI]

,

Evripidis Bampis

,

Chandra Chekuri

,

David R. Karger

,

,

,

,

Maurice Queyranne

,

Martin Skutella

,

,

Maxim Sviridenko

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

On Syntactic versus Computational Views of Approximability.

[BibT_eX]

[DOI]

,

,

,

Umesh V. Vazirani

SIAM J. Comput., 1998

On Certificates and Lookahead in Dynamic Graph Problems.

[BibT_eX]

[DOI]

,

,

Randall H. Wilson

Algorithmica, 1998

On Approximating Rectangle Tiling and Packing.

[BibT_eX]

[DOI]

,

S. Muthukrishnan

,

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

On Wireless Spectrum Estimation and Generalized Graph Coloring.

[BibT_eX]

[DOI]

Krishnan Kumaran

,

Proceedings of the Proceedings IEEE INFOCOM '98, The Conference on Computer Communications, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, Gateway to the 21st Century, San Francisco, CA, USA, March 29, 1998

1997

A Graph Partitioning Approach to Sequential Diagnosis.

[BibT_eX]

[DOI]

,

IEEE Trans. Computers, 1997

On the Hardness of Approximating Max k-Cut and its Dual.

[BibT_eX]

[DOI]

,

,

,

Alessandro Panconesi

Chic. J. Theor. Comput. Sci., 1997

A polynomial time approximation scheme for the SONET ring loading problem.

[BibT_eX]

[DOI]

Bell Labs Tech. J., 1997

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.

[BibT_eX]

[DOI]

,

,

David P. Williamson

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Efficient Array Partitioning.

[BibT_eX]

[DOI]

,

S. Muthukrishnan

,

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

A structural view of approximation.

[BibT_eX]

[DOI]

PhD thesis, 1996

Constraint satisfaction: The approximability of minimization problems.

[BibT_eX]

[DOI]

,

,

Electron. Colloquium Comput. Complex., 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

[BibT_eX]

[DOI]

,

,

David P. Williamson

Electron. Colloquium Comput. Complex., 1996

The Optimization Complexity of Constraint Satisfaction Problems

[BibT_eX]

[DOI]

,

Electron. Colloquium Comput. Complex., 1996

Towards a Syntactic Characterization of PTAS.

[BibT_eX]

[DOI]

,

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

A Linear Time Algorithm for Sequential Diagnosis in Hypercubes.

[BibT_eX]

[DOI]

,

J. Parallel Distributed Comput., 1995

1992

Multiprocessor Architectures for High Speed Networks: A Performance Study.

[BibT_eX]

,

,

C. Michael Overstreet

,

,

Mohammad Zubair

,

Proceedings of the Algorithms, Software, Architecture, 1992

Concurrent Use of Parallel Communication to Enable Remote Visualization.

[BibT_eX]

,

,

C. Michael Overstreet

,

,

Proceedings of the Computing and Information, 1992

Parallel TCP/IP for Multiprocessor Workstations.

[BibT_eX]

,

,

,

C. Michael Overstreet

,

Ramesh Yerraballi

,

Edwin C. Foudriat

,

Proceedings of the High Performance Networking IV, 1992

1991

Logic Programming for Software Verification and Testing.

[BibT_eX]

[DOI]

Comput. J., 1991

A carrier sensed multiple access protocol high data rate ring networks.

[BibT_eX]

[DOI]

Edwin C. Foudriat

,

,

C. Michael Overstreet

,

,

Comput. Commun. Rev., 1991

1990

Logic Programming for Software Testing.

[BibT_eX]

[DOI]

Proceedings of the Advances in Computing and Information, 1990

Loading...