We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime ...where 0<q<1. Consequently, we can sample random spanning forests in a graph and estimate the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has edge expansion at least 1.
Our algorithm and proof build on the recent results of Dinur, Kaufman, Mass and Oppenheim who show that a high dimensional walk on a weighted simplicial complex mixes rapidly if for every link of the complex, the corresponding localized random walk on the 1-skeleton is a strong spectral expander. One of our key observations is that a weighted simplicial complex X is a 0-local spectral expander if and only if a naturally associated generating polynomial pX is strongly log-concave. More generally, to every pure simplicial complex with positive weights on its maximal faces, we can associate to X a multiaffine homogeneous polynomial pX such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of pX.
Quantitative Algebraic Reasoning Mardare, Radu; Panangaden, Prakash; Plotkin, Gordon
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science,
07/2016
Conference Proceeding
Odprti dostop
We develop a quantitative analogue of equational reasoning which we call quantitative algebra. We define an equality relation indexed by rationals: a = ε b which we think of as saying that "a is ...approximately equal to b up to an error of ε ". We have 4 interesting examples where we have a quantitative equational theory whose free algebras correspond to well known structures. In each case we have finitary and continuous versions. The four cases are: Hausdorff metrics from quantitive semilattices; p-Wasserstein metrics (hence also the Kantorovich metric) from barycentric algebras and also from pointed barycentric algebras and the total variation metric from a variant of barycentric algebras.
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of ...evaluation queries.
We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a 1−1/e−є approximation for monotone functions and a 1/e−є approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is O(log2 n/є3), which is an exponential speedup over the existing algorithms.
We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a 1/e−є approximation using O(log(n/є) log(1/є) log(n+m)/ є2) parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a 1−1/e−є approximation in O(log(n/є)logm/є2) parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016).
Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.
We prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the ...spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λ<λc(Δ) where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Δ when the number of colors satisfies q > α Δ where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.
Our approach is based on two steps. First, we show that the approximate tensorization of entropy (i.e., factorizing entropy into single vertices), which is a key step for establishing the modified log-Sobolev inequality in many previous works, can be deduced from entropy factorization into blocks of fixed linear size. Second, we adapt the local-to-global scheme of Alev and Lau (2020) to establish such block factorization of entropy in a more general setting of pure weighted simplicial complexes satisfying local spectral expansion; this also substantially generalizes the result of Cryan et al. (2019).
We introduce the first complete and approximately universal diagrammatic language for quantum mechanics. We make the ZX-Calculus, a diagrammatic language introduced by Coecke and Duncan, complete for ...the so-called Clifford+T quantum mechanics by adding two new axioms to the language. The completeness of the ZX-Calculus for Clifford+T quantum mechanics -- also called the π/4-fragment of the ZX-Calculus -- was one of the main open questions in categorical quantum mechanics. We prove the completeness of this fragment using the recently studied ZW-Calculus, a calculus dealing with integer matrices. We also prove that the π/4-fragment of the ZX-Calculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.
We give an m1+o(1)βo(1)-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In the process, we illustrate how fundamental tradeoffs in ...graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix.
Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex v to the boundary of a set of vertices assigned to v called a “shortcutter.” We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter S to random walk steps in the Schur complement obtained by eliminating all vertices in S that are not assigned to it.
We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly(logn) depth and m poly(logn) work for n-nodes m-edges graphs. Although sequential ...algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1+ε)-approximation, all prior algorithms with poly(logn) depth perform at least Ω(mn c ) work for some constant c>0. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.
We develop several new tools of independent interest. One of them is a new notion beyond hopsets — low hop emulator — a poly(logn)-approximate emulator graph in which every shortest path has at most O(loglogn) hops (edges). Direct applications of the low hop emulators are parallel algorithms for poly(logn)-approximate single source shortest path (SSSP), Bourgain’s embedding, metric tree embedding, and low diameter decomposition, all with poly(logn) depth and m poly(logn) work.
To boost the approximation ratio to (1+ε), we introduce compressible preconditioners and apply it inside Sherman’s framework (SODA’17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a (1+ε)-approximate uncapacitated minimum cost flow in poly(logn) depth using m poly(logn) work. As a consequence, it also improves the state-of-the-art sequential running time from m· 2 O(√logn) to m poly(logn).
The undecidability of both typability and type checking for System F (polymorphic lambda-calculus) was established by Wells in the 1990s. For type checking Wells gave an astonishingly simple ...reduction from semi-unification (first-order unification combined with first-order matching). For typability Wells developed an intricate calculus to control the shape of type assumptions across type derivations via term structure. This calculus of invariant type assumptions allows for a reduction from type checking to typability. Unfortunately, this approach relies on heavy machinery that complicates surveyability of the overall argument.
The present work gives comparatively simple, direct reduction from semi-unification to System F typability. The key observation is as follows: in the existential setting of typability, it suffices to consider some specific (but not all, as for invariant type assumptions) type derivations. Additionally, the particular result requires only to consider closed types without nested quantification.
The undecidability of type checking is obtained via a folklore reduction from typability.
Profiting from its smaller footprint, correctness of the new approach is witnessed by a mechanization in the Coq proof assistant. The mechanization is incorporated into the existing Coq library of undecidability proofs. For free, the library provides constructive, mechanically verified many-one reductions from Turing machine halting to both System F typability and System F type checking.
Oracle separation of BQP and PH Raz, Ran; Tal, Avishay
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,
06/2019
Conference Proceeding
Recenzirano
Odprti dostop
We present a distribution D over inputs in {−1,1}2N, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O(logN), that distinguishes between ...D and the uniform distribution with advantage Ω(1/logN). (2) No Boolean circuit of quasi-polynomial size and constant depth distinguishes between D and the uniform distribution with advantage better than polylog(N)/√N.
By well known reductions, this gives a separation of the classes Promise-BQP and Promise-PH in the black-box model and implies an oracle O relative to which BQPO ⊈PHO.
In this paper we present a compositional model for distributed virtualized systems communicating over on-chip/off-chip deterministic networks implementing an end-to-end or partial time-triggered ...paradigm. We derive system-level constraints for combined task-, virtualization-and network-level static scheduling enabling the end-to-end composition of schedules for systems featuring table-driven (guest) operating systems. In the absence of a time-triggered run-time system, we analyze the composition problem with the aid of hierarchical scheduling methods for abstract resources. Moreover, we identify and discuss possible tradeoffs and optimization opportunities that arise when scheduling across multiple (virtualized) software layers in tandem with the deterministic network.
PDF
