| Publication | Date of Publication | Type |
|---|
Fully-dynamic graph sparsifiers against an adaptive adversary
| 2024-06-24 | Paper |
Approximating \(k\)-edge-connected spanning subgraphs via a near-linear time LP solver
| 2024-06-24 | Paper |
Fully dynamic exact edge connectivity in sublinear time
| 2024-05-14 | Paper |
Near-linear time approximations for cut problems via fair cuts
| 2024-05-14 | Paper |
Fast algorithms via dynamic-oracle matroids
| 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788488 (Why is no real title available?)
| 2024-01-15 | Paper |
Vertex connectivity in poly-logarithmic max-flows
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Breaking the quadratic barrier for matroid intersection
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Distributed weighted min-cut in nearly-optimal time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
SIAM Journal on Computing | 2023-10-26 | Paper |
Equivalence classes and conditional hardness in massively parallel computations
| 2023-02-07 | Paper |
Faster connectivity in low-rank hypergraphs via expander decomposition
| 2022-08-16 | Paper |
Equivalence classes and conditional hardness in massively parallel computations
Distributed Computing | 2022-04-01 | Paper |
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
SIAM Journal on Computing | 2022-01-07 | Paper |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
SIAM Journal on Computing | 2021-06-29 | Paper |
Coarse-Grained Complexity for Dynamic Algorithms
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Weighted min-cut: sequential, cut-query, and streaming algorithms
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
SIAM Journal on Computing | 2020-08-18 | Paper |
Distributed edge connectivity in sublinear time
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Distributed exact weighted all-pairs shortest paths in near-linear time
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Breaking quadratic time for small vertex connectivity and an approximation scheme
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
New tools and connections for exponential-time approximation
Algorithmica | 2019-09-10 | Paper |
A subquadratic-time algorithm for decremental single-source shortest paths
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Graph products revisited: tight approximation hardness of induced matching, poset dimension and more
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Journal of the ACM | 2019-02-25 | Paper |
Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks
ACM Transactions on Algorithms | 2018-11-12 | Paper |
Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
scientific article; zbMATH DE number 6850309 (Why is no real title available?)
| 2018-03-15 | Paper |
Distributed computation of large-scale graph problems
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
New deterministic approximation algorithms for fully dynamic matching
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
SIAM Journal on Computing | 2016-07-04 | Paper |
Faster algorithms for semi-matching problems
ACM Transactions on Algorithms | 2016-04-11 | Paper |
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Automata, Languages, and Programming | 2015-10-27 | Paper |
A tight unconditional lower bound on distributed randomwalk computation
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-09-11 | Paper |
Can quantum communication speed up distributed computation?
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
scientific article; zbMATH DE number 6469225 (Why is no real title available?)
| 2015-08-03 | Paper |
Distributed approximation algorithms for weighted shortest paths
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Efficient distributed random walks with applications
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-03-02 | Paper |
Almost-Tight Distributed Minimum Cut Algorithms
Lecture Notes in Computer Science | 2015-02-10 | Paper |
Polynomial-time algorithms for energy games with special weight structures
Algorithmica | 2015-01-19 | Paper |
Brief announcement
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Fast distributed random walks
Proceedings of the 28th ACM symposium on Principles of distributed computing | 2014-07-23 | Paper |
Distributed verification and hardness of distributed approximation
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
scientific article; zbMATH DE number 6292751 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2014-05-07 | Paper |
Simple FPTAS for the subset-sums ratio problem
Information Processing Letters | 2014-04-14 | Paper |
Coloring graph powers: graph product bounds and hardness of approximation
Lecture Notes in Computer Science | 2014-03-31 | Paper |
Distributed random walks
Journal of the ACM | 2014-02-17 | Paper |
An approximate restatement of the Four-Color Theorem
Journal of Graph Algorithms and Applications | 2013-10-29 | Paper |
Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks
Lecture Notes in Computer Science | 2013-08-07 | Paper |
Dense subgraphs on dynamic networks
Lecture Notes in Computer Science | 2013-03-13 | Paper |
Distributed verification and hardness of distributed approximation
SIAM Journal on Computing | 2013-02-04 | Paper |
Polynomial-time algorithms for energy games with special weight structures
Lecture Notes in Computer Science | 2012-09-25 | Paper |
Best-order streaming model
Theoretical Computer Science | 2011-05-18 | Paper |
Faster algorithms for semi-matching problems (extended abstract)
Automata, Languages and Programming | 2010-09-07 | Paper |
Best-Order Streaming Model
Lecture Notes in Computer Science | 2009-06-03 | Paper |
