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.

2011

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

2010

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

2009

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

2008

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

2007

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

Full version of the paper 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.

2006

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

Older Papers

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


• 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 to appear 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).


• 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 to appear 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.


• Why and Where: A Characterization of Data Provenance.
  (with P. Buneman and W. Tan)
  Proc. 8th International Conference on Database Theory (ICDT), 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 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 will appear 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.