More Like this

1. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

   https://doi.org/10.1145/3593809  

   Jambulapati, Arun; Sidford, Aaron (February 2024, ACM Transactions on Algorithms)

   In this paper we provide anO(mloglog^O(1)nlog (1/ϵ))-expected time algorithm for solving Laplacian systems onn-nodem-edge graphs, improving upon the previous best expected runtime of\(O(m \sqrt {\log n} \mathrm{log log}^{O(1)} n \log (1/\epsilon)) \)achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of low spectral stretch graph approximations with improved stretch and sparsity bounds. As motivation for this work, we show that for every set of vectors in\(\mathbb {R}^d \)(not just those induced by graphs) and all integerk> 1 there exist an ultra-sparsifier withd− 1 +O(d/k) re-weighted vectors of relative condition number at mostk². For smallk, this improves upon the previous best known multiplicative factor of\(k \cdot \tilde{O}(\log d) \), which is only known for the graph case. Additionally, in the graph case we employ our low-stretch subgraph construction to obtainn− 1 +O(n/k)-edge ultrasparsifiers of relative condition numberk^{1 +o(1)}fork=ω(log ^δn) for anyδ> 0: this improves upon the previous work fork=o(exp (log ^{1/2 −δ}n)). 

   more » « less
2. Streaming approximation resistance of every ordering CSP

   https://doi.org/10.1007/s00037-024-00252-5  

   Singer, Noah G; Sudan, Madhu; Velusamy, Santhoshini (June 2024, computational complexity)

   Abstract An ordering constraint satisfaction problem (OCSP) is defined by a family$$\mathcal F$$ $F$of predicates mapping permutations on$$\{1,\ldots,k\}$$ $\{1,\dots ,k\}$to$$\{0,1\}$$ $\{0,1\}$. An instance of ($$\mathcal F$$ $F$) onnvariables consists of a list of constraints, each consisting of a predicate from$$\mathcal F$$ $F$applied onkdistinct variables. The goal is to find an ordering of thenvariables that maximizes the number of constraints for which the induced ordering on thekvariables satisfies the predicate. OCSPs capture well-studied problems including ‘maximum acyclic subgraph’ () and “maximum betweenness”. In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every$$\mathcal F$$ $F$, ($$\mathcal F$$ $F$) is approximation-resistant to o(n)-space streaming algorithms, i.e., algorithms using o(n) space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of , our result shows that for every$$\epsilon>0$$ $ϵ>0$, is not$$(1/2+\epsilon)$$ $(1/2+ϵ)$-approximable in o(n) space. The previous best inapproximability result, due to Guruswami & Tao (2019), only ruled out 3/4-approximations in$$o(\sqrt n)$$ $o\left(\sqrt{n}\right)$space. Our results build on recent works of Chou et al. (2022b, 2024) who provide a tight, linear-space inapproximability theorem for a broad class of “standard” (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet sizeq) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for standard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following “partition expansion” property with high probability: For every partition of thenvariables into small blocks, for most of the constraints, all variables are in distinct blocks. 

   more » « less
3. An almost linear time algorithm testing whether the Markoff graph modulo p is connected

   https://doi.org/10.1007/s40993-024-00592-9  

   Brown, Colby Austin (March 2025, Research in Number Theory)

   Abstract The Markoff graphs modulopwere proven by Chen (Ann Math 199(1), 2024) to be connected for all but finitely many primes, and Baragar (The Markoff equation and equations of Hurwitz. Brown University, 1991) conjectured that they are connected for all primes, equivalently that every solution to the Markoff equation moduloplifts to a solution over$$\mathbb {Z}$$ $Z$. In this paper, we provide an algorithmic realization of the process introduced by Bourgain et al. [arXiv:1607.01530] to test whether the Markoff graph modulopis connected for arbitrary primes. Our algorithm runs in$$o(p^{1 + \epsilon })$$ $o\left(p^{1+ϵ}\right)$time for every$$\epsilon > 0$$ $ϵ>0$. We demonstrate this algorithm by confirming that the Markoff graph modulopis connected for all primes less than one million. 

   more » « less
4. Sketching Approximability of All Finite CSPs

   https://doi.org/10.1145/3649435  

   Chou, Chi-Ning; Golovnev, Alexander; Sudan, Madhu; Velusamy, Santhoshini (April 2024, Journal of the ACM)

   A constraint satisfaction problem (CSP),\(\textsf {Max-CSP}(\mathcal {F})\), is specified by a finite set of constraints\(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\)for positive integersqandk. An instance of the problem onnvariables is given bymapplications of constraints from\(\mathcal {F}\)to subsequences of thenvariables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family\(\mathcal {F}\)and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in\(o(\sqrt {n})\)space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case ofq=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of\(\mathcal {F}\)support a distribution on\([q]^k\)with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variablesq= 2, binary constraintsk=2, and singleton families\(|\mathcal {F}|=1\)and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [56], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to generalq-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes. 

   more » « less
5. Width Helps and Hinders Splitting Flows

   https://doi.org/10.1145/3641820  

   Cáceres, Manuel; Cairo, Massimo; Grigorjew, Andreas; Khan, Shahbaz; Mumey, Brendan; Rizzi, Romeo; Tomescu, Alexandru I.; Williams, Lucia (April 2024, ACM Transactions on Algorithms)

   Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulationXon a directed graphGinto weighted source-to-sink paths whose weighted sum equalsX. We show that, for acyclic graphs, considering thewidthof the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stablegraphs, for which a popular heuristic is aO(logVal(X))-approximation (Val(X) being the total flow ofX), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\)to Ω (m/logm) for sparse graphs, wheremis the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X‖ being the maximum absolute value ofXon any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version. 

   more » « less