| Publication | Date of Publication | Type |
|---|
| An efficient PTAS for stochastic load balancing with Poisson jobs | 2026-03-18 | Paper |
| Sublinear algorithms and lower bounds for metric TSP cost estimation | 2026-03-18 | Paper |
| Almost-tight bounds on preserving cuts in classes of submodular hypergraphs | 2026-01-14 | Paper |
| A faster combinatorial algorithm for maximum bipartite matching | 2024-11-28 | Paper |
| Parallel approximate maximum flows in near-linear work and polylogarithmic depth | 2024-11-28 | Paper |
| Code sparsification and its applications | 2024-11-28 | Paper |
| Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics | 2024-11-14 | Paper |
| New trade-offs for fully dynamic matching via hierarchical EDCS | 2024-07-19 | Paper |
| Query complexity of the metric Steiner tree problem | 2024-05-14 | Paper |
| Nearly tight bounds for discrete search under outlier noise | 2024-05-14 | Paper |
| On regularity lemma and barriers in streaming and dynamic matching | 2024-05-08 | Paper |
| scientific article; zbMATH DE number 7829325 (Why is no real title available?) | 2024-04-09 | Paper |
| scientific article; zbMATH DE number 7788515 (Why is no real title available?) | 2024-01-15 | Paper |
Graph connectivity and single element recovery via linear and OR queries
(available as arXiv preprint) | 2023-09-20 | Paper |
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
(available as arXiv preprint) | 2022-07-18 | Paper |
Top-\(k\) and clustering with noisy comparisons
ACM Transactions on Database Systems | 2021-11-25 | Paper |
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
Mathematical Programming. Series A. Series B | 2021-07-02 | Paper |
Tight bounds for single-pass streaming complexity of the set cover problem
SIAM Journal on Computing | 2021-06-29 | Paper |
On the Power of Planned Infections in Networks
Internet Mathematics | 2021-04-26 | Paper |
Space-efficient query evaluation over probabilistic event streams
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science | 2021-01-21 | Paper |
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Polynomial pass lower bounds for graph streaming algorithms
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
ACM Transactions on Algorithms | 2019-12-02 | Paper |
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
(available as arXiv preprint) | 2019-10-25 | Paper |
Sublinear algorithms for \((\Delta + 1)\) vertex coloring
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Stochastic submodular cover with limited adaptivity
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
Combinatorica | 2019-09-04 | Paper |
Disjoint set union with randomized linking
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Influence Maximization in Undirected Networks
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Approximating matching size from random streams
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| scientific article; zbMATH DE number 7053293 (Why is no real title available?) | 2019-05-10 | Paper |
| Perfect matchings via uniform sampling in regular bipartite graphs | 2019-05-06 | Paper |
| The ratio index for budgeted learning, with applications | 2019-05-06 | Paper |
Edge-disjoint paths revisited
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Sensitivity and computational complexity in financial networks
Algorithmic Finance | 2018-09-13 | Paper |
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
On estimating maximum matching size in graph streams
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Maximum matchings in dynamic graph streams and the simultaneous communication model
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| A faster algorithm for minimum-cost bipartite perfect matching in planar graphs | 2018-03-15 | Paper |
| Tight bounds on the round complexity of the distributed maximum coverage problem | 2018-03-15 | Paper |
Tight bounds on the round complexity of the distributed maximum coverage problem
(available as arXiv preprint) | 2018-03-15 | Paper |
Connectivity in random forests and credit networks
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
On \((1,\varepsilon)\)-restricted assignment makespan minimization
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Streaming Lower Bounds for Approximating MAX-CUT
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Tight bounds for single-pass streaming complexity of the set cover problem
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| Improved approximation results for stochastic knapsack problems | 2017-09-29 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Journal of Scheduling | 2017-09-01 | Paper |
Algorithms for provisioning queries and analytics
(available as arXiv preprint) | 2017-07-14 | Paper |
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
(available as arXiv preprint) | 2017-07-13 | Paper |
Strategic network formation with attack and immunization
Web and Internet Economics | 2017-02-10 | Paper |
Design networks with bounded pairwise distance
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Fast convergence in the double oral auction
Web and Internet Economics | 2016-01-08 | Paper |
Polynomial flow-cut gaps and hardness of directed cut problems
Journal of the ACM | 2015-11-11 | Paper |
| scientific article; zbMATH DE number 6472596 (Why is no real title available?) | 2015-08-14 | Paper |
| Randomized pursuit-evasion with limited visibility | 2015-08-03 | Paper |
| Reconstructing strings from random traces | 2015-08-03 | Paper |
Approximability of capacitated network design
Algorithmica | 2015-07-10 | Paper |
Approximability of capacitated network design
Algorithmica | 2015-07-10 | Paper |
Algorithms for minimizing weighted flow time
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
On the power of adversarial infections in networks
Lecture Notes in Computer Science | 2015-01-13 | Paper |
Edge-disjoint paths in planar graphs with constant congestion
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Hardness of cut problems in directed graphs
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Approximation algorithms for data placement on parallel disks
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Perfect matchings via uniform sampling in regular bipartite graphs
ACM Transactions on Algorithms | 2014-11-18 | Paper |
| Approximating the average response time in broadcast scheduling | 2014-10-13 | Paper |
Perfect matchings in \(O(n \log n)\) time in regular bipartite graphs
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Delays and the Capacity of Continuous-Time Channels
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Algorithms for the Generalized Sorting Problem
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
On allocating goods to maximize fairness
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Dynamic and non-uniform pricing strategies for revenue maximization
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
A Utility Equivalence Theorem for Concave Functions
Integer Programming and Combinatorial Optimization | 2014-06-02 | Paper |
Dynamic and nonuniform pricing strategies for revenue maximization
SIAM Journal on Computing | 2014-04-11 | Paper |
The all-or-nothing multicommodity flow problem
SIAM Journal on Computing | 2013-11-14 | Paper |
Perfect matchings in \(O(n\log n)\) time in regular bipartite graphs
SIAM Journal on Computing | 2013-09-25 | Paper |
Distributed private heavy hitters
Automata, Languages, and Programming | 2013-08-12 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Lecture Notes in Computer Science | 2013-06-07 | Paper |
Improved hardness results for profit maximization pricing problems with unlimited supply
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
| STCON in directed unique-path graphs | 2012-10-19 | Paper |
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
Theory of Computing | 2012-09-27 | Paper |
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
Combinatorica | 2011-12-19 | Paper |
Optimal lower bounds for universal and differentially private Steiner trees and TSPs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Optimal lower bounds for universal and differentially private Steiner trees and TSPs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Social welfare in one-sided matching markets without money
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Approximability of capacitated network design
Integer Programming and Combinatoral Optimization | 2011-06-24 | Paper |
scientific article; zbMATH DE number 5899246 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Multicommodity flow, well-linked terminals, and routing problems
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
The all-or-nothing multicommodity flow problem
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Approximation schemes for preemptive weighted flow time
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Robust self-assembly of graphs
Natural Computing | 2010-05-05 | Paper |
Edge-disjoint paths in planar graphs with constant congestion
SIAM Journal on Computing | 2010-03-17 | Paper |
Nash dynamics in constant player and bounded jump congestion games
Algorithmic Game Theory | 2009-12-01 | Paper |
Robust Self-assembly of Graphs
DNA Computing | 2009-11-10 | Paper |
A note on multiflows and treewidth
Algorithmica | 2009-08-27 | Paper |
The network as a storage device: dynamic routing with bounded buffers
Algorithmica | 2009-07-24 | Paper |
| scientific article; zbMATH DE number 5485528 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485450 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485449 (Why is no real title available?) | 2009-01-05 | Paper |
Asymmetric k -center is log * n -hard to approximate
Journal of the ACM | 2008-12-21 | Paper |
Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data
Lecture Notes in Computer Science | 2008-09-09 | Paper |
Algorithms for 2-Route Cut Problems
Automata, Languages and Programming | 2008-08-28 | Paper |
On the complexity of graph self-assembly in accretive systems
Natural Computing | 2008-07-31 | Paper |
A Formal Investigation of Diff3
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science | 2008-04-24 | Paper |
On the Complexity of Graph Self-assembly in Accretive Systems
DNA Computing | 2008-04-04 | Paper |
Efficient Enumeration of Phylogenetically Informative Substrings
Lecture Notes in Computer Science | 2007-08-30 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
SIAM Journal on Computing | 2006-06-01 | Paper |
Randomized Pursuit-Evasion with Local Visibility
SIAM Journal on Discrete Mathematics | 2006-06-01 | Paper |
| scientific article; zbMATH DE number 2209775 (Why is no real title available?) | 2005-09-28 | Paper |
Directed Network Design with Orientation Constraints
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
On the Hardness of 4-Coloring a 3-Colorable Graph
SIAM Journal on Discrete Mathematics | 2005-02-28 | Paper |
On Multidimensional Packing Problems
SIAM Journal on Computing | 2005-02-21 | Paper |
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
Journal of Computer and System Sciences | 2004-08-19 | Paper |
| scientific article; zbMATH DE number 2086617 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2080193 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2080480 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2079316 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079393 (Why is no real title available?) | 2004-07-28 | Paper |
Time-constrained scheduling of weighted packets on trees and meshes
Algorithmica | 2003-08-17 | Paper |
| A deterministic algorithm for the cost-distance problem | 2003-07-29 | Paper |
| scientific article; zbMATH DE number 1775432 (Why is no real title available?) | 2002-08-01 | Paper |
| scientific article; zbMATH DE number 1775453 (Why is no real title available?) | 2002-08-01 | Paper |
| scientific article; zbMATH DE number 1754639 (Why is no real title available?) | 2002-06-12 | Paper |
| Approximation algorithms for the metric labeling problem via a new linear programming formulation | 2002-03-24 | Paper |
Complexity classifications of Boolean constraint satisfaction problems
SIAM Monographs on Discrete Mathematics and Applications | 2001-07-03 | Paper |
On the hardness of approximating the chromatic number
Combinatorica | 2001-06-12 | Paper |
The approximability of constraint satisfaction problems
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1559517 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1445306 (Why is no real title available?) | 2001-01-15 | Paper |
| scientific article; zbMATH DE number 1445363 (Why is no real title available?) | 2000-10-23 | Paper |
On indexed data broadcast
Journal of Computer and System Sciences | 2000-08-27 | Paper |
| scientific article; zbMATH DE number 1305407 (Why is no real title available?) | 2000-06-21 | Paper |
| scientific article; zbMATH DE number 1305507 (Why is no real title available?) | 2000-06-13 | Paper |
| scientific article; zbMATH DE number 1445355 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1445307 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1305389 (Why is no real title available?) | 2000-04-13 | Paper |
On Broadcast Disk Paging
SIAM Journal on Computing | 2000-03-19 | Paper |
The Angular-Metric Traveling Salesman Problem
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1332666 (Why is no real title available?) | 1999-09-08 | Paper |
| scientific article; zbMATH DE number 1256750 (Why is no real title available?) | 1999-03-01 | Paper |
On Syntactic versus Computational Views of Approximability
SIAM Journal on Computing | 1998-09-21 | Paper |
On certificates and lookahead in dynamic graph problems
Algorithmica | 1998-08-02 | Paper |
| scientific article; zbMATH DE number 871918 (Why is no real title available?) | 1996-04-28 | Paper |
A linear time algorithm for sequential diagnosis in hypercubes
Journal of Parallel and Distributed Computing | 1995-07-06 | Paper |
