Publications — Sanjeev Khanna

Book Chapters, Surveys, and Thesis

Quantiles and Equidepth Histograms over Streams.
(with M. Greenwald)
In Data Stream Management: Processing High-Speed Data Streams, ed. M. Garofalakis, J. Gehrke, and R. Rastogi, Springer, 2016. (Note that this survey has not been updated since 2007 or so, and hence does not contain many interesting subsequent developments.)

Complexity classifications of Boolean constraint satisfaction problems.
(with N. Creignou and M. Sudan) In SIGACT News, Volume 32, Number 4, Whole Number 121, Complexity Theory Column 34, pages 24-33, November 2001.

A Structural View of Approximation.
Ph.D. Thesis, Stanford University, 1996.

Papers

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness.
(with A. Padaki and E. Waingarten).
In 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2026.

On the Parallel Complexity of Finding a Matroid Basis.
(with A. Putterman and J. Song).
In Proc. 66th IEEE Symposium on Foundations of Computer (FOCS), 2025.

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams.
(with A. Padaki, K. Singal, and E. Waingarten)
In Proc. 66th IEEE Symposium on Foundations of Computer (FOCS), 2025.

Stochastic Knapsack without Relaxing the Capacity.
(with A. De and N. White)
In Proc. 66th IEEE Symposium on Foundations of Computer (FOCS), 2025.

Streaming Maximal Matching with Bounded Deletions.
(with C. Konrad and J. Dark).
In Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP), 2025.

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity.
(with I. Bansal, J. Cheriyan, and M. Simmons).
In Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP), 2025.

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams.
(with A. Putterman and M. Sudan).
In Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP), 2025.

A Theory of Spectral CSP Sparsification.
(with A. Putterman and M. Sudan).
In Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP), 2025.

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification.
(with H. Li and A. Putterman).
In Proc. 57th ACM Symposium on Theory of Computing (STOC), 2025.

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms.
(with S. Assadi and A. Putterman).
In Proc. 57th ACM Symposium on Theory of Computing (STOC), 2025.

Efficient Algorithms and New Characterizations for CSP Sparsification.
(with A. Putterman and M. Sudan).
In Proc. 57th ACM Symposium on Theory of Computing (STOC), 2025.

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs.
(with S. Assadi and P. Kiss).
In 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.

Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers.
(with A. Putterman and M. Sudan).
In Proc. 65th IEEE Symposium on Foundations of Computer (FOCS), 2024.

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs.
(with A. Putterman and M. Sudan).
In Proc. 51st International Colloquium on Automata, Languages, and Programming (ICALP), 2024.

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm.
(with J. Chuzhoy).
In Proc. 56th ACM Symposium on Theory of Computing (STOC), 2024.
(Invited to the SICOMP special issue devoted to STOC 2024.)

A Faster Combinatorial Algorithm for Maximum Bipartite Matching.
(with J. Chuzhoy).
In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
(Invited to HALG 2024.)

Code Sparsification and its Applications.
(with A. Putterman and M. Sudan).
In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth.
(with A. Agarwal, H. Li, P. Patil, C. Wang, N. White, and P. Zhong).
In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.

On Regularity Lemma and Barriers in Streaming and Dynamic Matching.
(with S. Assadi, S. Behnezhad, and H. Li).
In Proc. 55th ACM Symposium on Theory of Computing (STOC), 2023.

Set Cover in the One-pass Edge-arrival Streaming Model.
(with C. Konrad and C. Alexandru)
Proc. 42nd ACM Symposium on Principles of Database Systems (PODS), 2023.

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics.
(with Y. Chen and Z. Tan).
In Proc. 50th International Colloquium on Automata, Languages, and Programming (ICALP), 2023.

Query Complexity of the Metric Steiner Tree Problem.
(with Y. Chen and Z. Tan).
In 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

Sublinear Algorithms for Hierarchical Clustering.
(with A. Agarwal, H. Li, and P. Patil).
In 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.

On Weighted Graph Sparsification by Linear Sketching.
(with Y. Chen and H. Li).
In Proc. 63rd IEEE Symposium on Foundations of Computer (FOCS), 2022.

A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits.
(with A. Agarwal and P. Patil).
In Conference On Learning Theory (COLT), 2022.

PAC Top-k Identification under SST in Limited Rounds.
(with A. Agarwal and P. Patil).
In 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.

Optimal Bounds for Dominating Set in Graph Streams.
(with C. Konrad).
In 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022.

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS.
(with S. Behnezhad).
In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

Nearly Tight Bounds for Discrete Search under Outlier Noise.
(with A. De, H. Li, and H. Nikpey).
In Fifth Symposium on Simplicity in Algorithms (SOSA), 2022.

Approximate optimization of convex functions with outlier noise.
(with A. De, H. Li, and H. Nikpey).
In 35th Conference on Neural Information Processing Systems (NeurIPS), 2021.

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization.
(with Y. Chen and D. Chakrabarty).
In Proc. 62nd IEEE Symposium on Foundations of Computer (FOCS), 2021.

Graph Connectivity and Single Element Recovery via Linear and OR Queries.
(with S. Assadi and D. Chakrabarty).
In Proc. 29th Annual European Symposium on Algorithms (ESA), 2021.

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries.
(with Y. Chen and A. Nagda).
In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021.

Hardness of Approximation for Orienteering with Multiple Time Windows.
(with N. Garg and A. Kumar).
In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.

Near-linear Size Hypergraph Cut Sparsifiers.
(with Y. Chen and A. Nagda).
In Proc. 61st IEEE Symposium on Foundations of Computer (FOCS), 2020.

Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions.
(with A. Agarwal, S. Agarwal, and P. Patil,).
In Proc. 37th International Conference on Machine Learning (ICML), 2020.

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation.
(with Y. Chen and S. Kannan).
In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP), 2020.

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs.
(with A. De, H. Li, and H. Nikpey).
In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP), 2020.

Space-efficient Query Evaluation over Probabilistic Event Streams.
(with R. Alur, Y. Chen, and K. Jothimurugan).
In 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2020.

Near-Perfect Recovery in the One-Dimensional Latent Space Model.
(with Y. Chen and S. Kannan).
In The Web Conference (WWW), 1932--1942, 2020.

Network Formation under Random Attack and Probabilistic Spread.
(with Y. Chen, S. Jabbari, M. J. Kearns, and J. Morgenstern).
In Proc. 28th International Joint Conference on Artificial Intelligence (IJCAI), 180--186, 2019.

A New Algorithm for Decremental Single-source shortest Paths with Applications to Vertex-capacitated Cut and Flow Problems.
(with J. Chuzhoy).
In Proc. 51st ACM Symposium on Theory of Computing (STOC), 2019.

Polynomial Pass Lower Bounds for Graph Streaming Algorithms.
(with S. Assadi and Y. Chen).
In Proc. 51st ACM Symposium on Theory of Computing (STOC), 2019.

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.
(with S. Assadi and M. Kapralov).
In 10th Innovations in Theoretical Computer Science (ITCS), 2019.

Sublinear Algorithms for (Δ +1) Vertex Coloring.
(with S. Assadi and Yu Chen).
In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
(Winner of the best paper award.)

Stochastic Submodular Cover with Limited Adaptivity.
(with A. Agarwal and S. Assadi).
In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

Testing Graph Clusterability: Algorithms and Lower Bounds.
(with A. Chiplunkar, M. Kapralov, A. Mousavifar, and Y. Peres).
In Proc. 59th IEEE Symposium on Foundations of Computer (FOCS), 2018.

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
(with D. Chakrabarty).
In First Symposium on Simplicity in Algorithms (SOSA), 2018.

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.
(with S. Assadi).
In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.

A Faster Algorithm for the Minimum-Cost Bipartite Perfect Matching in Planar Graphs.
(with M. K. Asathulla, N. Lahn and S. Raghvendra.).
In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.

Randomized Composable Coresets for Matching and Vertex Cover.
(with S. Assadi).
In 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017.
(Co-winner of the best paper award.)

Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.
(with A. Agarwal, S. Agarwal, and S. Assadi).
In Conference On Learning Theory (COLT), 2017.

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm.
(with S. Assadi and Y. Li).
In Proc. 18th ACM Conference on Electronic Commerce (EC), 2017.

StreamQRE: Modular Specification and Efficient Evaluation of Quantitative Queries over Streaming Data.
(with K. Mamouras, M. Raghotaman, R. Alur, and Z. Ives).
In ACM Conference on Programming Language Design and Implementation (PLDI), 2017.

On Estimating Maximum Matching Size in Graph Streams.
(with S. Assadi and Y. Li).
In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.

(1 + Ω(1))-Approximation to MAX-CUT Requires Linear Space.
(with M. Kapralov, M. Sudan and A. Velingker).
In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.

Strategic Network Formation with Attack and Immunization.
(with S. Goyal, S. Jabbari, M. Kearns, and J. Morgenstern).
In 12th Workshop on Internet and Network Economics (WINE), 2016.

Sensitivity and Computational Complexity in Financial Networks.
(with B. Hemenway).
To appear in Algorithmic Finance.

The Stochastic Matching Problem With (Very) Few Queries.
(with S. Assadi and Y. Li).
Proc. 17th ACM Conference on Electronic Commerce (EC), pp. 43-60, 2016.

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem.
(with S. Assadi and Y. Li).
Proc. 48th ACM Symposium on Theory of Computing (STOC), pp. 698-711, 2016.
(Invited to the SICOMP special issue devoted to STOC 2016.)

Rapid Convergence versus Policy Expressiveness in Interdomain Routing.
(with A. Gurney and Y. Li).
IEEE International Conference on Computer Communications (INFOCOM), pp. 1-9, 2016.

Algorithms for Provisioning Queries and Analytics.
(with S. Assadi, Y. Li, and V. Tannen).
19th International Conference on Database Theory (ICDT), pp. 1-18, 2016.

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.
(with S. Assadi, Y. Li, and G. Yaroslavtsev).
Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1345-1364, 2016.

Fast Convergence in the Double Oral Auction.
(with S. Assadi, Y. Li, and R. Vohra).
Proc. 11th Workshop on Internet and Network Economics (WINE), pp. 60-73, 2015.
(Winner of the best paper award.)

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches.
(with S. Assadi, Y. Li, and V. Tannen).
35th FSTTCS, pp. 52-68, 2015.

Streaming Lower Bounds for Approximating MAX-CUT.
(with M. Kapralov and Madhu Sudan).
Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

On (1,eps)-Restricted Assignment Makespan Minimization.
(with D. Chakrabarty and S. Li).
Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

Connectivity in Random Forests and Credit Networks.
(with A. Goel, S. Raghvendra, and H. Zhang).
Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

Approximating Matching Size from Random Streams.
(with M. Kapralov and Madhu Sudan).
Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

Influence Maximization in Undirected Networks.
(with B. Lucier)
Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

Disjoint Set Union with Randomized Linking.
(with A. Goel, D. Larkin, and R. Tarjan).
Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

On the Power of Adversarial Infections in Networks.
(with M. Brautbar and M. Draief).
10th Workshop on Algorithms and Models for the Web Graph (WAW), 2013.

Using the Crowd for Top-k and Group-by Queries.
(with S. Davidson, T. Milo, and S. Roy).
16th International Conference on Database Theory (ICDT), 2013.

A Special Case of Restricted Assignment Makespan Minimization}.
(with D. Chakrabarty)
11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013.

A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
(with M. Chrobak, U. Feige, M. T. Hajiaghayi, F. Li, and S. Naor)
8th International Conference on Algorithms and Complexity (CIAC), 2013

The Power of Local Information in Social Networks.
(with C. Borgs, M. Brautbar, J. Chayes, and B. Lucier) Proc. 8th Workshop on Internet and Network Economics (WINE), pp. 406-419, 2012.

On the Communication and Streaming Complexity of Maximum Bipartite Matching.
(with A. Goel and M. Kapralov).
Proc. 23rd Annual Symposium on Discrete Algorithms (SODA), 2012.

Distributed Private Heavy Hitters.
(with J. Hsu and A. Roth).
Proc. 39th International Colloquium on Automata, Languages, and Programming (ICALP), 2012.

Improved Hardness Results for Profit Maximization Problems with Unlimited Supply.
(with P. Chalermsook, J. Chuzhoy, and S. Kannan).
APPROX, 2012.

Algorithms for the Generalized Sorting Problem.
(with Z. Huang and S. Kannan).
Proc. 52nd IEEE Symposium on Foundations of Computer (FOCS), 2011.

Delays and the Capacity of Continuous-time Channels.
(with M. Sudan).
Proc. 52nd IEEE Symposium on Foundations of Computer (FOCS), 2011.

Improved Approximation results for Stochastic Knapsack Problems.
(with A. Bhalgat and A. Goel).
Proc. 22nd Annual Symposium on Discrete Algorithms (SODA), 2011.

Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.
(with A. Bhalgat and D. Chakrabarty).
APPROX, 2011.

Social Welfare in One-Sided Matching Markets without Money.
(with A. Bhalgat and D. Chakrabarty)
APPROX, 2011.

Approximability of Capacitated Network Design.
(with D. Chakrabarty, C. Chekuri and N. Korula)
IPCO, 2011.

Queries with Difference on Probabilistic Databases.
(with S. Roy and V. Tannen)
Proc. 37th International Conference on Very Large Databases, (VLDB), 2011.

Provenance Views for Module Privacy.
(with S. Davidson, T. Milo, D. Panigrahi, and S. Roy)
Proc. 30th ACM Symposium on Principles of Database Systems (PODS), 175-186, 2011.

On Provenance and Privacy.
(with S. Davidson, S. Roy, J. Stoyanovich, V. Tannen, and Y. Chen)
Proc. 14th International Conference on Database Theory (ICDT), 3-10, 2011.

Compression Without a Common Prior: An Information-theoretic Justification for Ambiguity in Language.
(with B. Juba, A. Kalai, and M. Sudan).
Proc. 2nd Symposium on Innovations in Computer Science (ICS), 2011.

Perfect Matchings in O(n lg n) Time in Regular Bipartite Graphs.
(with A. Goel and M. Kapralov).
Proc. 42nd ACM Symposium on Theory of Computing (STOC), 2010.

Approximating Pure Nash Equilibrium in Cut, Party Affiliation, and Satisfiability Games.
(with A. Bhalgat and T. Chakraborty).
Proc. 11th ACM Conference on Electronic Commerce (EC), pp. 73--82, 2010.

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
(with P. Briest, P. Chalermsook, B. Laekhanukit, and D. Nanongkai).
Proc. 6th Workshop on Internet and Network Economics (WINE), pp. 444-454, 2010.

An Optimal Labeling Scheme for Workflow Provenance Using Skelton Labels
(with Z. Bao, S. Davidson, and S. Roy).
ACM SIGMOD International Conference on Management of Data (SIGMOD), 711-722, 2010.

Privacy Issues in Scientific Workflow Provenance
(with S. Boulakia, S. Davidson, and S. Roy).
Workshop on Workflow Approaches for New Data-centric Science (WANDS), 2010.

Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs
(with M. Andrews, J. Chuzhoy, V. Guruswami, K. Talwar, L. Zhang)
Combinatorica, 30(5): 485-520, 2010.

On Allocating Goods to Maximize Fairness.
(with D. Chakrabarty and J. Chuzhoy).
Proc. 50th IEEE Symposium on Foundations of Computer (FOCS), 2009.

An O(k^{3} log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
(with J. Chuzhoy).
Proc. 50th IEEE Symposium on Foundations of Computer (FOCS), 2009.

Dynamic and Non-uniform Pricing Strategies for Revenue Maximization.
(with T. Chakraborty and Z. Huang).
Proc. 50th IEEE Symposium on Foundations of Computer (FOCS), 2009.

Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs.
(with A. Goel and M. Kapralov).
Proc. 20th Annual Symposium on Discrete Algorithms (SODA), 2009.
Full version appears in special issue of ACM Transactions on Algorithms (TALG), devoted to SODA 2009 papers.

The Ratio Index for Budgeted Learning, with Applications.
(with A. Goel and B. Null).
Proc. 20th Annual Symposium on Discrete Algorithms (SODA), 2009.

Network Bargaining: Algorithms and Structural Results.
(with T. Chakraborty and M. Kearns).
Proc. 10th ACM Conference on Electronic Commerce (EC), 2009.

Differencing Provenance in Scientific Workflows
(with Z. Bao, S. Boulakia, S. Davidson, and A. Eyal).
Proc. 25th Conference on Data Engineering (ICDE), 808-819, 2009.

Optimizing User Views for Workflows.
(with O. Biton, S. Davidson, and S. Roy)
Proc. 12th International Conference on Database Theory (ICDT), 2009.

Algorithms for Single-Source Vertex-Connectivity.
(with J. Chuzhoy).
Proc. 49th IEEE Symposium on Foundations of Computer (FOCS), 2008.

Algorithms for 2-Route Cut Problems.
(with Chandra Chekuri)
Proc. 35th International Colloquium on Automata, Languages, and Programming (ICALP), 2008.

Network Design for Vertex Connectivity.
(with T. Chakraborty and J. Chuzhoy).
40th ACM Symposium on Theory of Computing (STOC), 2008.

Robust Self-assembly of Graphs.
(with S. Angelov and M. Visontai)
DNA 2008.

STCON in Directed Unique-Path Graphs.
(with S. Kannan and S. Roy)
FSTTCS 2008.

Adaptive SelectiveVerification.
(with S. Venkatesh, O. Fatemieh, F. Khan and C. Gunter)
INFOCOM 2008.

On the Network Coding Advantage for Wireless Multicast in Euclidean Space.
(with A. Goel)
IPSN 2008.

Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems.
(with J. Chuzhoy).
39th ACM Symposium on Theory of Computing (STOC), 2007.

Full version appears in Journal of the ACM (JACM), 56(2), 2009.

Hardness of Routing with Congestion in Directed Graphs.
(with J. Chuzhoy, V. Guruswami, and K. Talwar).
39th ACM Symposium on Theory of Computing (STOC), 2007.

A Formal Investigation of Diff3.
(with K. Kunal and B. Pierce).
FSTTCS, 485-496, 2007.

Efficient Enumeration of Phylogenetically Informative Substrings.
(with S. Angelov, B. Hard, S. Kannan, and J. Kim).
Journal of Computational Biology, 14(6), 701-723, 2007.

Hardness of Cut Problems in Directed Graphs.
(with J. Chuzhoy).
38th ACM Symposium on Theory of Computing (STOC), 2006.

Edge-Disjoint Paths in Planar Graphs with Constant Congestion.
(with C. Chekuri and F. B. Shepherd).
38th ACM Symposium on Theory of Computing (STOC), 2006.

Hardness of Directed Routing with Congestion.
(with J. Chuzhoy).
ECCC Report, 2006.

Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data.
(with M. B. Greenwald, K. Kunal, B. C. Pierce, and A. Schmitt)
21st International Symposium on DIStributed Computing (DISC), 2006, pp. 269--28.

On the Complexity of Graph Self-Assembly in Accretive Systems.
(with S. Angelov and M. Visontai)
12th International Meeting on DNA Computing (DNA), 2006, pp. 95--110.

Efficient Enumeration of Phylogenetically Informative Strings.
(with S. Angelov, B. Harb, S. Kannan, and J. Kim)
10th Conference on Research in Computational Biology (RECOMB), 2006.

Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
(with M. Andrews, J. Chuzhoy, and L. Zhang).
Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005.

New Hardness Results for Undirected Edge-Disjoint Paths.
(with J. Chuzhoy).
Manuscript, 2005.

Multicommodity flow, well-linked terminals, and routing problems.
(with C. Chekuri and F. B. Shepherd).
37th ACM Symposium on Theory of Computing (STOC), 2005.

Edge Disjoint Paths in Planar Graphs.
(with C. Chekuri and F. B. Shepherd).
Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), 2004.

Machine Minimization for Scheduling Jobs with Interval Constraints.
(with J. Chuzhoy, S. Guha, and S. Naor).
Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), 2004.

Asymmetric k-center is log^*n-hard to Approximate.
(with J. Chuzhoy, S. Guha, E. Halperin, G. Kortsarz, R. Krauthgamer, and S. Naor).
36th ACM Symposium on Theory of Computing (STOC), 2004.

The All-or-Nothing Multicommodity Flow Problem.
(with C. Chekuri and F. B. Shepherd).
36th ACM Symposium on Theory of Computing (STOC), 2004.
Full version appears in SICOMP, 2013.

Multi-processor Scheduling to Minimize Flowtime with eps Resource Augmentation.
(with C. Chekuri, A. Goel, and A. Kumar).
36th ACM Symposium on Theory of Computing (STOC), 2004.

Approximating Longest Directed Paths and Cycles.
(with Andreas Björklund and Thore Husfeldt)
Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP), 2004.

Power-Conserving Computation of Order-Statistics over Sensor Networks.
(with M. Greenwald).
23rd ACM Symposium on Principles of Database Systems (PODS), 275-285, 2004.

Randomized pursuit-evasion with limited visibility.
(with V. Isler and S. Kannan).
Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp. 1060-1069, 2004.

Reconstructing strings from random traces.
(with T. Batu, S. Kannan, and A. McGregor).
Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp. 910-918, 2004.

Edge Disjoint Paths Revisited.
(with C. Chekuri).
Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003.

Selection with Monotone Comparison Costs.
(with S. Kannan)
Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003.

Approximation Schemes for Preemptive Weighted Flow Time.
(with C. Chekuri).
34th ACM Symposium on Theory of Computing (STOC), 2002.

On Propagation of Deletions and Annotations through Views.
(with P. Buneman and W. Tan).
21st ACM Symposium on Principles of Database Systems (PODS), 2002.

Archiving Scientific Data.
(with P. Buneman, K. Tajima, and W. Tan.)
ACM SIGMOD International Conference on Management of Data (SIGMOD), 2002.

On Computing Functions with Uncertainity.
(with W. Tan)
Proc. 20th ACM Symposium on Principles of Database Systems (PODS), 2001.

Space-Efficient Online Computation of Online Summaries.
(with M. Greenwald)
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), 2001.

Algorithms for Minimizing Weighted Flow Time.
(with C. Chekuri and A. Zhu)
Proc. 33rd ACM Symposium on Theory of Computing (STOC), pp. 84-93, 2001.

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.
(with C. Chekuri)
28th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 848--861, 2001.

Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation.
(with C. Chekuri, S. Naor, and L. Zosin)
Proc. 12th Annual Symposium on Discrete Algorithms (SODA), pp. 109-118, 2001.
Full version appears in SIAM Journal on Discrete Mathematics (SIDMA).

A Deterministic Algorithm for the Cost-Distance Problem.
(with C. Chekuri and S. Naor) Proc. 12th Annual Symposium on Discrete Algorithms (SODA), pp. 232-233, 2001 (short form).

Why and Where: A Characterization of Data Provenance.
(with P. Buneman and W. Tan)
Proc. 8th International Conference on Database Theory (ICDT), 2001.

A PTAS for the Multiple Knapsack Problem.
(with C. Chekuri)
Proc. 11th Annual Symposium on Discrete Algorithms (SODA), pp. 213-222, 2000.

Directed Network Design Problems with Orientation Constraints.
(with J. Naor and F.B. Shepherd)
Proc. 11th Annual Symposium on Discrete Algorithms (SODA), pp. 663-671, 2000.
Full version appears in SIAM Journal on Discrete Mathematics (SIDMA).

Approximation Algorithms for Data Placement on Parallel Disks.
(with L. Golubchik, S. Khuller, R. Thurimella and A. Zhu)
Proc. 11th Annual Symposium on Discrete Algorithms (SODA), pp. 223-232, 2000.

Watermarking Maps: Hiding Information in Structured Data.
(with F. Zane)
Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.

On the Hardness of $4$-coloring a $3$-colorable Graph.
(with V. Guruswami)
Proc. 15th IEEE Computational Complexity Conference (CCC), pp. 188-197, 2000.
Full version appears in SIAM Journal on Discrete Mathematics (SIDMA), 18(1), 30-40, 2004.

Data Provenance: Some Basic Issues.
(with P. Buneman and W. Tan)
Proc. 8th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2000.

Approximation Schemes for Scheduling to Minimize Average Completion Time with Release Dates.
(with F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, I. Milis, M. Queyranne, M. Skutella, C. Stein and M. Sviridenko)
Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 32-44, 1999.

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.
(with M. Adler, R. Rajaraman and A. Rosen)
Proc. 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1-12, 1999.
Algorithmica 36(2): 123-152, 2003.

Near-Optimal Hardness Results and Approximation Algorithms for
Edge-Disjoint Paths and Related Problems.
(with V. Guruswami, B. Shepherd, R. Rajaraman and M. Yannakakis)
Proc. 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 19-28, 1999.

Designing Networks with Bounded Pairwise Distance.
(with Y. Dodis)
Proc. 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750-759, 1999.

On Multidimensional Packing Problems.
(with C. Chekuri)
Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 185-194, 1999.
Full version appears in SIAM Journal on Computing (SICOMP).

Page Replacement for General Caching Problems.
(with S. Albers and S. Arora)
Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 31-40, 1999.

The 2-Catalog Segmentation Problem
(with Y. Dodis and V. Guruswami)
Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 897-898, 1999 (Short Form).

Space-Time Tradeoffs for Graph Properties.
(with Y. Dodis)
Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP), 1999.

Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch.
(with M. Andrews and K. Kumaran)
Proc. 18th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 1999.

On Indexed Data Broadcast.
(with S. Zhou)
Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 463-472, 1998.
Full version appears in special issue of Journal of Computer and System Sciences (JCSS), devoted to STOC 98 papers.

On Broadcast Disk Paging.
(with V. Liberatore)
Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), 1998, pp. 634-643.
Full version appears in SIAM Journal on Computing (SICOMP).

On Wireless Spectrum Estimation and Generalized Graph Coloring.
(with K. Kumaran)
Proc. 17th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 1998.

On Approximating Rectangle Tiling and Packing.
(with S. Muthukrishnan and M. Paterson)
Proc. 9th Annual Symposium on Discrete Algorithms (SODA), pp. 384-393, 1998.

A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem.
Bell Labs Technical Journal, Spring Issue, pp. 36-41, 1997.
Also appeared in INFORMS 98.

Efficient Array Partitioning.
(with S. Muthukrishnan and S. Skiena)
Proc. 24th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 616-626, 1997.

Angular-Metric TSP.
(with A. Aggarwal, D. Coppersmith, R. Motwani and B. Schieber)
Proc. 8th Annual Symposium on Discrete Algorithms (SODA), pp. 221-229, 1997.
Full version appears in SIAM Journal on Computing (SICOMP).

A Graph Partitioning Approach to Sequential Diagnosis.
(with W. K. Fuchs)
IEEE Transactions on Computers (IEEETC), January 1997, pp. 39-47.

On the Hardness of Max $k$-Cut and its Dual.
(with V. Kann, J. Lagergren and A. Panconesi)
Proc. 5th Israel Symposium on Theory and Computing Systems (ISTCS), 1996, pp. 61-67.
Full version appears in Chicago Journal of Theoretical Computer Science (CJTCS), 1997.

Towards a Syntactic Characterization of PTAS.
(with R. Motwani)
Proc. 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 329-337, 1996.

On Certificates and Lookahead in Dynamic Graph Problems.
(with R. Motwani and R. Wilson)
Proc. 7th Annual Symposium on Discrete Algorithms (SODA), 1996, pp. 222-231.
Full version appears in Algorithmica (1998) Vol. 21, pp. 377-394.

A Linear Time Sequential Diagnosis Algorithm for Hypercubes.
(with W. K. Fuchs)
Journal of Parallel and Distributed Computing (JPDC), April 1995, pp. 48-53.

Approximation Algorithms for the Largest Common Subtree Problem.
(with R. Motwani and F.F. Yao)
Stanford University Tech. Report STAN-CS-TR-95-1545 , 1995.

On Syntactic versus Computational Views of Approximability.
(with R. Motwani, M. Sudan and U. Vazirani)
Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 819-830, 1994.
Full version appears in SIAM Journal on Computing (SICOMP), Vol. 28, No. 1, pp. 164-191, 1999.

On the Hardness of Approximating the Chromatic Number.
(with N. Linial and S. Safra)
Proc. 2nd Israel Symposium on Theory and Computing Systems (ISTCS),
1993, pp. 250-260.