Teaching Algorithm Design: A Literature Review
Potential Research Topics
Dynamic Vertex Connectivity
For very small connectivity (subpolynomial)
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
Deterministic Small Vertex Connectivity in Almost Linear Time
For larger connectivity that requires reduction to max-flow
Dynamic Maxflow via Dynamic Interior Point Methods
TSP
Faster Approximations for Metric-TSP via Linear Programming, reduction from fraction to approximate
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time
Sorrachai Simpler Packing Covering MwU Note
Maroid Intersection
Congest Lower Bound Using Rounds vs. Bits Complexity
Future Goals
- Check whether recent breakthrough for max flow imply congest lower bound or not.
Related Papers
Polynomial Pass Lower Bounds for Graph Streaming Algorithms. [Assadi, Chen, Khanna, STOC'19]
Large Vertex Connectivity
Two party communication is tight.
Streaming: I guess the reduction to BMM is tight, so we should wait for the BMM to be tight in streaming.
CONGEST: I guess the reduction is not tight, current running time is $n^{2/3}T_{BMM}^{1/3}$.
Quantum query: not tight, current upper bound is $n^{11/6}$ while lower bound is $n^{1.5}$. I suspect the lower bound should be higher.
Related Papers
Congest small Edge/Vertex Connectivity
Future Goals
- Explore the complexity of computing small undirected unweighted Edge/Vertex connectivity in congest model. I guess the complexity should be $\Theta(kD)$.
Related Papers
Distributed Connectivity Decomposition [Censor-Hillel, Ghaffari, Kuhn, PODC'15]
Near-Optimal Distributed Computation of Small Vertex Cuts [Parter, Petruschka, DISC'22]
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach [Parter,DISC'19]
Sequential local vertex cut / directed edge cut
The current best upper bound is $O(\mu k^2)$ and lower bound is $\Omega(\mu k)$.
Related Papers
Distributed/Parallel Negative Weighted SSSP
Future Goals
- The current reduction has a $n^{o(1)}$ factor, we want to reduce it to $polylog(n)$.
Related Papers
Triangle Detection in CONGEST (Clique) Model
breaking the $O(n^{1/3})$ upper bound in congest model (or even congest clique, but not allowed to use fast matrix multiplication).
Strong sublinear time algorithm in CONGEST model
Elkin’s paper gives a truly sublinear round algorithm for shortest path in congest model.
For bipartite matching, the O(nlog n) round algorithm is not for weighted graph.
The $O(n)$ commmunication protocol for BMM cite requires $O(log W)$.
General question: consider “strong running time” in distributed, parallel or other models.
Strong polynomial time negative weight shortest path via max-flow
There was a reduction to max-flow which lose a $O(m)$ factor, the open problem is to improve that reduction.
https://link.springer.com/content/pdf/10.1007/bf02579200.pdf
https://www.jstor.org/stable/170819
https://dl.acm.org/doi/10.1145/3383454
lower bounds for dynamic query model
prove lower bound for the paper Fast Algorithms via Dynamic-Oracle Matroids
Hard Problems
Streaming Space vs. Passes Lower Bound for Reachability
Future Goals
- Ultimate goal: $n^{\epsilon}$ passes is nessesary for $n^{1+\epsilon}$ space.
Related Papers
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms [Assadi, Raz, FOCS'20]
Superlinear lower bounds for multipass graph processing [Guruswami, Onak, CCC'13]
Directed Edge Connectivity
Faster Algorithms for Rooted Connectivity in Directed Graphs[Chekuri, Quanrud, ICALP'21]
Submodular Function Minimization
Minimizing Convex Functions with Integral Minimizers [Jiang, SODA'21]