More Like this

1. Counting and Sampling Orientations on Chordal Graphs

   https://doi.org/10.1007/978-3-030-96731-4_29  

   Bezakova, Ivona ; Sun, Wenbo ( January 2022 , International Conference and Workshops on Algorithms and Computation (WALCOM))

   We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs, motivating our study on a restricted, yet well-studied, graph class. Our main focus is source-sink-free orientations, a natural restricted version of sink-free orientations related to strong orientations, which we introduce in this work. These orientations are intriguing, since despite their similarity, currently known FPRAS and sampling techniques (such as Markov chains or sink-popping) that apply to sink-free orientations do not seem to apply to source-sink-free orientations. We present fast polynomialtime algorithms counting these orientations on chordal graphs. Our approach combines dynamic programming with inclusion-exclusion (going two levels deep for source-sink-free orientations and one level for sinkfree orientations) throughout the computation. Dynamic programming counting algorithms can be typically used to produce a uniformly random sample. However, due to the negative terms of the inclusion-exclusion, the typical approach to obtain a polynomial-time sampling algorithm does not apply in our case. Obtaining such an almost uniform sampling algorithm for source-sink-free orientations in chordal graphs remains an open problem. Little is known about counting or sampling of acyclic or bipolar orientations, even on restricted graph classes. We design efficient (linear-time) exact uniform sampling algorithms for these orientations on chordal graphs. These algorithms are a byproduct of our counting algorithms, but unlike in other works that provide dynamic-programming-based samplers, we produce a random orientation without computing the corresponding count, which leads to a faster running time than the counting algorithm (since it avoids manipulation of large integers). 

   more » « less
2. More on zeros and approximation of the Ising partition function

   https://doi.org/10.1017/fms.2021.40  

   Barvinok, Alexander ; Barvinok, Nicholas ( January 2021 , Forum of Mathematics, Sigma)

   Abstract We consider the problem of computing the partition function $\sum _x e^{f(x)}$ , where $f: \{-1, 1\}^n \longrightarrow {\mathbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{-1, 1\}^n$ . In the case of a quadratic polynomial f , we show that the partition function can be approximated within relative error $0 < \epsilon < 1$ in quasi-polynomial $n^{O(\ln n - \ln \epsilon )}$ time if the Lipschitz constant of the non-linear part of f with respect to the $\ell ^1$ metric on the Boolean cube does not exceed $1-\delta $ , for any $\delta>0$ , fixed in advance. For a cubic polynomial f , we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum _x e^{\tilde {f}(x)} \ne 0$ for complex-valued polynomials $\tilde {f}$ in a neighborhood of a real-valued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices. 

   more » « less
3. Perturbation of elliptic operators in 1-sided NTA domains satisfying the capacity density condition

   https://doi.org/10.1515/forum-2022-0323  

   Akman, Murat ; Hofmann, Steve ; Martell, José María ; Toro, Tatiana ( December 2022 , Forum Mathematicum)

   Abstract Let Ω ⊂ ℝ n + 1 {\Omega\subset\mathbb{R}^{n+1}} , n ≥ 2 {n\geq 2} , be a 1-sided non-tangentially accessible domain (aka uniform domain), that is, Ω satisfies the interior Corkscrew and Harnack chain conditions, which are respectively scale-invariant/quantitative versions of openness and path-connectedness. Let us assume also that Ω satisfies the so-called capacity density condition, a quantitative version of the fact that all boundary points are Wiener regular. Consider L 0 ⁢ u = - div ⁢ ( A 0 ⁢ ∇ ⁡ u ) {L_{0}u=-\mathrm{div}(A_{0}\nabla u)} , L ⁢ u = - div ⁢ ( A ⁢ ∇ ⁡ u ) {Lu=-\mathrm{div}(A\nabla u)} , two real (non-necessarily symmetric) uniformly elliptic operators in Ω, and write ω L 0 {\omega_{L_{0}}} , ω L {\omega_{L}} for the respective associated elliptic measures. The goal of this program is to find sufficient conditions guaranteeing that ω L {\omega_{L}} satisfies an A ∞ {A_{\infty}} -condition or a RH q {\mathrm{RH}_{q}} -condition with respect to ω L 0 {\omega_{L_{0}}} . In this paper we establish that if the discrepancy of the two matrices satisfies a natural Carleson measure condition with respect to ω L 0 {\omega_{L_{0}}} , then ω L ∈ A ∞ ⁢ ( ω L 0 ) {\omega_{L}\in A_{\infty}(\omega_{L_{0}})} . Additionally, we can prove that ω L ∈ RH q ⁢ ( ω L 0 ) {\omega_{L}\in\mathrm{RH}_{q}(\omega_{L_{0}})} for some specific q ∈ ( 1 , ∞ ) {q\in(1,\infty)} , by assuming that such Carleson condition holds with a sufficiently small constant. This “small constant” case extends previous work of Fefferman–Kenig–Pipher and Milakis–Pipher together with the last author of the present paper who considered symmetric operators in Lipschitz and bounded chord-arc domains, respectively. Here we go beyond those settings, our domains satisfy a capacity density condition which is much weaker than the existence of exterior Corkscrew balls. Moreover, their boundaries need not be Ahlfors regular and the restriction of the n -dimensional Hausdorff measure to the boundary could be even locally infinite. The “large constant” case, that is, the one on which we just assume that the discrepancy of the two matrices satisfies a Carleson measure condition, is new even in the case of nice domains (such as the unit ball, the upper-half space, or non-tangentially accessible domains) and in the case of symmetric operators. We emphasize that our results hold in the absence of a nice surface measure: all the analysis is done with the underlying measure ω L 0 {\omega_{L_{0}}} , which behaves well in the scenarios we are considering. When particularized to the setting of Lipschitz, chord-arc, or 1-sided chord-arc domains, our methods allow us to immediately recover a number of existing perturbation results as well as extend some of them. 

   more » « less
4. Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

   https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.15  

   Kale, Sagar ; Tirodkar, Sumedh ( August 2017 , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques)

   We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we are able to achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely—we give a (2/3 − ε)- approximation algorithm that uses 2/(3ε) passes for triangle-free graphs and 4/(3ε) passes for general graphs. Our algorithms are simple and combinatorial, use O(n log n) space, and (can be implemented to) have O(1) update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: * Ahn and Guha give a (2/3−ε)-approximation algorithm that uses O(log(1/ε)/ε2) passes, whereas our (2/3 − ε)-approximation algorithm uses 4/(3ε) passes; * they also give a (1 − ε)-approximation algorithm that uses O(log n · poly(1/ε)) passes, where n is the number of vertices of the input graph; although our algorithm is (2/3−ε)-approximation, our number of passes do not depend on n. Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3. 

   more » « less
5. Tight Bounds for ℓ 1 Oblivious Subspace Embeddings

   https://doi.org/10.1145/3477537  

   Wang, Ruosong ; Woodruff, David P. ( January 2022 , ACM Transactions on Algorithms)

   An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications. 

   more » « less