In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: Certifying that a list of Counting the number of Computing the All-Pairs Shortest Distances matrix for an Certifying that an Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time
Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution to
Extending computational harmonic analysis tools from the classical setting of regular lattices to the more general setting of graphs and networks is very important, and much research has been done recently. The generalized Haar–Walsh transform (GHWT) developed by Irion and Saito (2014) is a multiscale transform for signals on graphs, which is a generalization of the classical Haar and Walsh–Hadamard transforms. We propose the
- PAR ID:
- 10364195
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Journal of Mathematical Imaging and Vision
- Volume:
- 64
- Issue:
- 3
- ISSN:
- 0924-9907
- Page Range / eLocation ID:
- p. 261-283
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract n integers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$ $$\tilde{O}(n^{1.5})$$ $$\tilde{O}(n^{1.5})$$ $$\tilde{O}(n^{1.5})$$ k -cliques with total edge weight equal to zero in ann -node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$ $$k\ge 3$$ k , this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm -edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$ k -cliques in unweighted graphs, and had worse running times for smallk .n -node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$ $$\Omega (n^2)$$ $$\tilde{O}(n^{2.94})$$ n -variablek -CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$ $$2^{n/2}\cdot \textrm{poly}(n)$$ $$\#$$ k -UNSAT running in$$2^{n/2}/n^{\omega (1)}$$ $$2^{4n/5}\cdot \textrm{poly}(n)$$ $$2^{2n/3}\cdot \textrm{poly}(n)$$ n integers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$ $$2^{0.49991n}\cdot \textrm{poly}(n)$$ -
more » « less
Abstract Approximate integer programming is the following: For a given convex body
$$K \subseteq {\mathbb {R}}^n$$ $$K \cap {\mathbb {Z}}^n$$ $$2\cdot (K - c) +c$$ K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time$$2^{O(n)}$$ $$2^{O(n)} \cdot n^n$$ $$x^* \in (K \cap {\mathbb {Z}}^n)$$ $$2^{O(n)}$$ remainders of each component$$x_i^* \mod \ell $$ $$\ell \ge 5(n+1)$$ $$x^*$$ cutting-plane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$ asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range $$0 \le x_i \le p(n)$$ $$(\log n)^{O(n)}$$ $$n^n \cdot 2^{O(n)}$$ -
more » « less
Abstract A graph
G isH -free if it has no induced subgraph isomorphic toH . We prove that a$$P_5$$ $$\omega \ge 3$$ $$\omega ^{\log _2(\omega )}$$ $$(5/27)3^{\omega }$$ $$P_5$$ $$P_5$$ -
more » « less
Abstract Given a monotone submodular set function with a knapsack constraint, its maximization problem has two types of approximation algorithms with running time
$$O(n^2)$$ $$O(n^5)$$ $$O(n^5)$$ $$1-1/e$$ $$O(n^2)$$ $$(1-1/e)/2$$ $$(1-1/e^2)/2$$ $$O(n^2)$$ $$1-1/e^{2/3}$$ $$O(n^3)$$ -
more » « less
Abstract Given a compact doubling metric measure space
X that supports a 2-Poincaré inequality, we construct a Dirichlet form on$$N^{1,2}(X)$$ $$N^{1,2}(X)$$ X by a family of graphs that is doubling and supports a 2-Poincaré inequality (see [20]). We construct a bilinear form on$$N^{1,2}(X)$$ $$\Gamma $$ $$\mathcal {E}$$ $$\mathcal {E}$$ X . Properties of$$\mathcal {E}$$ $$\mathcal {E}$$ $$\Omega \subseteq X$$ $$\mathcal {E}$$ X with a prescribed Lipschitz boundary data via a numerical scheme dictated by the approximating Dirichlet forms, which are discrete objects.
