- arXiv.org
- Biological Physics
- Applied Physics
- History and Philosophy of Physics
- Data Analysis, Statistics and Probability
- Fluid Dynamics
- Optics
- Physics and Society
- General Physics
- Popular Physics
- Space Physics
- Plasma Physics
- Atomic Physics
- Medical Physics
- Atomic and Molecular Clusters
- Physics Education
- Accelerator Physics
- Computational Physics
- Classical Physics
- Atmospheric and Oceanic Physics
- Instrumentation and Detectors
- Geophysics
- Chemical Physics

- History and Overview
- General Mathematics
- Analysis of PDEs
- Statistics Theory
- Number Theory
- Information Theory
- Combinatorics
- Representation Theory
- Mathematical Physics
- Probability
- Algebraic Geometry
- Operator Algebras
- Group Theory
- Complex Variables
- Symplectic Geometry
- General Topology
- Dynamical Systems
- Optimization and Control
- Numerical Analysis
- Geometric Topology
- Quantum Algebra
- Logic
- Differential Geometry
- Metric Geometry
- Algebraic Topology
- K-Theory and Homology
- Functional Analysis
- Commutative Algebra
- Category Theory
- Classical Analysis and ODEs
- Spectral Theory
- Rings and Algebras

- General Literature
- Neural and Evolutionary Computing
- Hardware Architecture
- Information Theory
- Symbolic Computation
- Mathematical Software
- Operating Systems
- Learning
- Computer Vision and Pattern Recognition
- Information Retrieval
- Multiagent Systems
- Social and Information Networks
- Formal Languages and Automata Theory
- Sound
- Databases
- Software Engineering
- Programming Languages
- Artificial Intelligence
- Other Computer Science
- Computational Complexity
- Discrete Mathematics
- Computer Science and Game Theory
- Cryptography and Security
- Human-Computer Interaction
- Numerical Analysis
- Systems and Control
- Distributed, Parallel, and Cluster Computing
- Emerging Technologies
- Robotics
- Computation and Language
- Data Structures and Algorithms
- Multimedia
- Computational Geometry
- Logic in Computer Science
- Computers and Society
- Networking and Internet Architecture
- Performance
- Computational Engineering, Finance, and Science
- Digital Libraries
- Graphics

- We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length $m$ and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an $O(m^{1/2-\varepsilon})$ time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.
- We study the recently introduced problem of finding dense common subgraphs: Given a sequence of graphs that share the same vertex set, the goal is to find a subset of vertices $S$ that maximizes some aggregate measure of the density of the subgraphs induced by $S$ in each of the given graphs. Different choices for the aggregation function give rise to variants of the problem that were studied recently. We settle many of the questions left open by previous works, showing NP-hardness, hardness of approximation, non-trivial approximation algorithms, and an integrality gap for a natural relaxation.
- Landau-Ginzburg mirror symmetry studies isomorphisms between graded Frobenius algebras, known as A- and B-models. Fundamental to constructing these models is the computation of the finite, Abelian maximal symmetry group $G_{W}^{\max}$ of a given polynomial $W$. For invertible polynomials, which have the same number of monomials as variables, a generating set for this group can be computed efficiently by inverting the polynomial exponent matrix. However, this method does not work for noninvertible polynomials with more monomials than variables since the resulting exponent matrix is no longer square. In this paper we present and analyze two characterizations of the maximal symmetry group that address this problem--one based on submatrices of the exponent matrix, and the other based on the Smith normal form of the exponent matrix. We analyze the resulting algorithms based on these characterizations, demonstrating the efficiency of the latter and the intractability of the former.
- We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to points on the boundary of the region, place the remaining vertices to create a planar straight-line drawing of the graph inside the region. This strengthens an NP-hardness result by Patrignani on extending partial planar graph drawings. Our result is one of the first showing that a problem of drawing planar graphs with straight-line edges is hard for the existential theory of the reals. The complexity of the problem is open in the case of a simply connected region. We also show that, even for integer input coordinates, it is possible that drawing a graph in a polygonal region requires some vertices to be placed at irrational coordinates. By contrast, the coordinates are known to be bounded in the special case of a convex region, or for drawing a path in any polygonal region.
- It is demonstrated that the classical Hough transform with shift-elevation parametrization of digital straight lines has additive complexity of at most $\mathcal{O}(n^3 / \log n)$ on a $n\times n$ image. The proof is constructive and uses ensemble computation approach to build summation circuits. The proposed method has similarities with the fast Hough transform (FHT) and may be considered a form of the "divide and conquer" technique. It is based on the fact that lines with close slopes can be decomposed into common components, allowing generalization for other pattern families. When applied to FHT patterns, the algorithm yields exactly the $\Theta(n^2\log n)$ FHT asymptotics which might suggest that the actual classical Hough transform circuits could smaller size than $\Theta(n^3/ \log n)$.
- This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.
- Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus maximisation, which strives to find the model parameters that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack of fundamental analysis of the problem in the computer vision literature. In particular, whether consensus maximisation is "tractable" remains a question that has not been rigorously dealt with, thus making it difficult to assess and compare the performance of proposed algorithms, relative to what is theoretically achievable. To shed light on these issues, we present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem, and resolve several ambiguities existing in the literature.
- The trace of matrix functions, often called spectral sums, e.g., rank, log-determinant and nuclear norm, appear in many machine learning tasks. However, optimizing or computing such (parameterized) spectral sums typically involves the matrix decomposition at the cost cubic in the matrix dimension, which is expensive for large-scale applications. Several recent works were proposed to approximate large-scale spectral sums utilizing polynomial function approximations and stochastic trace estimators. However, all prior works on this line have studied biased estimators, and their direct adaptions to an optimization task under stochastic gradient descent (SGD) frameworks often do not work as accumulated biased errors prevent stable convergence to the optimum. To address the issue, we propose the provable optimal unbiased estimator by randomizing Chebyshev polynomial degrees. We further introduce two additional techniques for accelerating SGD, where key ideas are on sharing randomness among many estimations during the iterative procedure. Finally, we showcase two applications of the proposed SGD schemes: matrix completion and learning Gaussian process, under the real-world datasets.
- We develop an randomized approximation algorithm for the size of set union problem $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$, which given a list of sets $A_1,...,A_m$ with approximate set size $m_i$ for $A_i$ with $m_i\in \left((1-\beta_L)|A_i|, (1+\beta_R)|A_i|\right)$, and biased random generators with $Prob(x=\randomElm(A_i))\in \left[{1-\alpha_L\over |A_i|},{1+\alpha_R\over |A_i|}\right]$ for each input set $A_i$ and element $x\in A_i,$ where $i=1, 2, ..., m$. The approximation ratio for $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$ is in the range $[(1-\epsilon)(1-\alpha_L)(1-\beta_L), (1+\epsilon)(1+\alpha_R)(1+\beta_R)]$ for any $\epsilon\in (0,1)$, where $\alpha_L, \alpha_R, \beta_L,\beta_R\in (0,1)$. The complexity of the algorithm is measured by both time complexity, and round complexity. The algorithm is allowed to make multiple membership queries and get random elements from the input sets in one round. Our algorithm makes adaptive accesses to input sets with multiple rounds. Our algorithm gives an approximation scheme with $O(\setCount\cdot(\log \setCount)^{O(1)})$ running time and $O(\log m)$ rounds, where $m$ is the number of sets. Our algorithm can handle input sets that can generate random elements with bias, and its approximation ratio depends on the bias. Our algorithm gives a flexible tradeoff with time complexity $O\left(\setCount^{1+\xi}\right)$ and round complexity $O\left({1\over \xi}\right)$ for any $\xi\in(0,1)$.
- Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular, independent sets and colourings. In this article we study the complexity of $\#_p\mathsf{H}$OMS$\mathsf{T}$O$H$, the problem of counting graph homomorphisms from an input graph to a graph $H$ modulo a prime number $p$. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the input graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. However, in subsequent studies on counting modulo $2$ the influence, the structure of $H$ has on the tractability, was shown to persist, yielding similar dichotomies. Our main result shows that for every tree $H$ and every prime $p$ the problem $\#_p\mathsf{H}$OMS$\mathsf{T}$O$H$ is either polynomial time computable or $\#_p\mathsf{P}$-complete. This addresses the conjecture of Faben and Jerrum stating this dichotomy for every graph $H$ when counting modulo 2. In order to prove this result, we study the structural properties of a homomorphism. As an important interim, this study yields a dichotomy for the problem of weighted counting independent sets in a bipartite graph modulo some prime $p$. Our results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo~2 case but for the modular counting functions of all primes $p$.

Quantum advantage with shallow circuits

Robin Blume-Kohout Apr 07 2017 20:30 UTCDavid Gosset Apr 06 2017 20:11 UTC

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak Webb Apr 06 2017 17:15 UTC

...(continued)You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guaran

Robin Blume-Kohout Apr 06 2017 15:05 UTC

...(continued)Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allo

Steve Flammia Apr 04 2017 13:13 UTC

I would like to publicly thank the authors for using the term "advantage" instead of the tainted word "supremacy" that makes me cringe every time I hear it.

Also, great result!

Ashley Apr 04 2017 08:35 UTC

A provable separation between analogous quantum and classical circuit classes!

Māris Ozols Feb 21 2017 15:35 UTC

...(continued)I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

Jānis Iraids Jan 25 2017 11:35 UTC

You are correct, that is a mistake -- it should be $\\{0,1\\}^n\rightarrow\\{0,1\\}$. Thank you for spotting it!

Christopher Chubb Jan 25 2017 02:27 UTC

In the abstract, should the domain of $f$ be $\lbrace0,1\rbrace^n$ instead of just $\lbrace0,1\rbrace$?

Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

- Supported by Silverpond.