Publications
Book Chapters and Surveys

Quantiles and Equidepth Histograms over Streams.
(with M. Greenwald)
In Data Stream Management: Processing HighSpeed 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 2433, November 2001.
Papers

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

Learning with Limited Rounds of Adaptivity: Coin Tossing, MultiArmed 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 NonAdaptive 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).
To appear in 28th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2017.

(1 + Ω(1))Approximation to MAXCUT Requires Linear Space.
(with M. Kapralov, M. Sudan and A. Velingker).
To appear in 28th Annual ACMSIAM 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. 4360, 2016.

Tight Bounds for SinglePass Streaming Complexity of the Set Cover Problem.
(with S. Assadi and Y. Li).
Proc. 48th ACM Symposium on Theory of Computing (STOC), pp. 698711, 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. 19, 2016.

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

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.
(with S. Assadi, Y. Li, and G. Yaroslavtsev).
Proc. 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 13451364, 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. 6073, 2015.
(Recipient of the best paper award)

Dynamic Sketching for Graph Optimization Problems with Applications to CutPreserving Sketches.
(with S. Assadi, Y. Li, and V. Tannen).
35th FSTTCS, pp. 5268, 2015.

Streaming Lower Bounds for Approximating MAXCUT.
(with M. Kapralov and Madhu Sudan).
Proc. 26th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2015.

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

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

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

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

Disjoint Set Union with Randomized Linking.
(with A. Goel, D. Larkin, and R. Tarjan).
Proc. 25th Annual ACMSIAM 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 Topk and Groupby 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 MinimumGap 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. 406419, 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 Continuoustime 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 OneSided 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), 175186, 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), 310, 2011.

Compression Without a Common Prior: An Informationtheoretic 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. 7382, 2010.

Improved Hardness of Approximation for Stackelberg ShortestPath Pricing.
(with P. Briest, P. Chalermsook, B. Laekhanukit, and D. Nanongkai).
Proc. 6th Workshop on Internet and Network Economics (WINE), pp. 444454, 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), 711722, 2010.

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

Inapproximability of EdgeDisjoint Paths and Low Congestion Routing on Undirected Graphs
(with M. Andrews, J. Chuzhoy, V. Guruswami, K. Talwar, L. Zhang)
Combinatorica, 30(5): 485520, 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 VertexConnectivity Survivable Network Design.
(with J. Chuzhoy).
Proc. 50th IEEE Symposium on Foundations of Computer (FOCS), 2009.

Dynamic and Nonuniform 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), 808819, 2009.

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

Polynomial FlowCut 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, 485496, 2007.

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

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

EdgeDisjoint 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. 26928.

On the Complexity of Graph SelfAssembly in Accretive Systems.
(with S. Angelov and M. Visontai)
12th International Meeting on DNA Computing (DNA), 2006, pp. 95110.

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 EdgeDisjoint 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 EdgeDisjoint Paths.
(with J. Chuzhoy).
Manuscript, 2005.

Multicommodity flow, welllinked 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 kcenter is log^*nhard 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 AllorNothing 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.

Multiprocessor 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.

PowerConserving Computation of OrderStatistics over Sensor Networks.
(with M. Greenwald).
23rd ACM Symposium on Principles of Database Systems (PODS), 275285, 2004.

Randomized pursuitevasion with limited visibility.
(with V. Isler and S. Kannan).
Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp.
10601069, 2004.

Reconstructing strings from random traces.
(with T. Batu, S. Kannan, and A. McGregor).
Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp.
910918, 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.

SpaceEfficient 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. 8493, 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. 848861, 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. 109118, 2001.
Full version appears in SIAM Journal on Discrete Mathematics (SIDMA).

A Deterministic Algorithm for the CostDistance Problem.
(with C. Chekuri and S. Naor)
Proc. 12th Annual Symposium on Discrete Algorithms (SODA), pp. 232233,
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. 213222,
2000.

Directed Network Design Problems with Orientation Constraints.
(with J. Naor and F.B. Shepherd)
Proc. 11th Annual Symposium on Discrete Algorithms (SODA), pp. 663671, 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. 223232,
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. 188197, 2000.
Full version appears in SIAM Journal on Discrete Mathematics (SIDMA), 18(1), 3040, 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. 3244, 1999.

TimeConstrained 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. 112, 1999.
Algorithmica 36(2): 123152, 2003.

NearOptimal Hardness Results and Approximation Algorithms for
EdgeDisjoint 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. 1928, 1999.

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

On Multidimensional Packing Problems.
(with C. Chekuri)
Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp.
185194, 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.
3140, 1999.

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

SpaceTime 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
InputQueued 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. 463472, 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. 634643.
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. 384393, 1998.

A Polynomial Time Approximation Scheme for the SONET Ring Loading
Problem.
Bell Labs Technical Journal, Spring Issue, pp. 3641, 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. 616626, 1997.

AngularMetric TSP.
(with A. Aggarwal, D. Coppersmith, R. Motwani and B. Schieber)
Proc. 8th Annual Symposium on Discrete Algorithms (SODA), pp.
221229, 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. 3947.

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. 6167.
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. 329337, 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.
222231.
Full version appears in Algorithmica (1998) Vol. 21, pp. 377394.

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

Approximation Algorithms for the Largest Common Subtree Problem.
(with R. Motwani and F.F. Yao)
Stanford University Tech. Report STANCSTR951545 , 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. 819830, 1994.
Full version appears in SIAM Journal on Computing (SICOMP), Vol. 28, No. 1, pp.
164191, 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. 250260.