cs.CC

arXiv:2501.12365v1 Announce Type: new Abstract: Computing the Fourier transform of a $q$-ary function $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$, which maps $q$-ary sequences to real numbers, is an important problem in mathematics with wide-ranging applications in biology, signal processing, and machine learning. Previous studies have shown that, under the sparsity assumption, the Fourier transform can be computed efficiently using fast and sample-efficient algorithms. However, in many practical settings, the function is defined over a more general space -- the space of generalized $q$-ary sequences $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$ -- where each $\mathbb{Z}_{q_i}$ corresponds to integers modulo $q_i$. A naive approach involves setting $q=\max_i{q_i}$ and treating the function as $q$-ary, which results in heavy computational overheads. Herein, we develop GFast, an algorithm that computes the $S$-sparse Fourier transform of $f$ with a sample complexity of $O(Sn)$, computational complexity of $O(Sn \log N)$, and a failure probability that approaches zero as $N=\prod_{i=1}^n q_i \rightarrow \infty$ with $S = N^\delta$ for some $0 \leq \delta 25\%$ smaller normalized mean-squared error compared to existing algorithms.

arXiv:2501.12062v1 Announce Type: new Abstract: Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an $\ell$-colouring of a $k$-colourable $r$-uniform hypergraph is NP-hard for all constant $2\leq k\leq \ell$ and $r\geq 3$. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an $\ell$-conflict-free colouring of an $r$-uniform hypergraph that admits a $k$-conflict-free colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, except for $r=4$ and $k=2$ (and any $\ell$); this case is solvable in polynomial time. The case of $r=3$ is the standard nonmonochromatic colouring, and the case of $r=2$ is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an $\ell$-linearly-ordered colouring of an $r$-uniform hypergraph that admits a $k$-linearly-ordered colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, thus improving on the results of Nakajima and \v{Z}ivn\'y~[ICALP'22/ACM TocT'23].

arXiv:2208.14739v5 Announce Type: replace Abstract: The class of Basic Feasible Functionals BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit characterizations of BFF based on a typed programming language of terms. These terms may perform calls to non-recursive imperative procedures. The type discipline has two layers: the terms follow a standard simply-typed discipline and the procedures follow a standard tier-based type discipline. BFF consists exactly of the second-order functionals that are computed by typable and terminating programs. The completeness of this characterization surprisingly still holds in the absence of lambda-abstraction. Moreover, the termination requirement can be specified as a completeness-preserving instance, which can be decided in time quadratic in the size of the program. As typing is decidable in polynomial time, we obtain the first tractable (i.e., decidable in polynomial time), sound, complete, and implicit characterization of BFF, thus solving a problem opened for more than 20 years.

arXiv:2501.12260v1 Announce Type: new Abstract: Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to indentify interesting classes of groups for which equation satisfiability problem is solvable in (probabilistic) polynomial-time. Based on these results, we present a full characterization of groups, for which the identity checking problem has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present full description of finite algebras from congruence modular varieties for which testing circuit equivalence can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis.

arXiv:2501.11683v1 Announce Type: new Abstract: Flesh and Blood (FAB) is a trading card game that two players need to make a strategy to reduce the life points of their opponent to zero. The mechanics of the game present complex decision-making scenarios of resource management. Due the similarity of other card games, the strategy of the game have scenarios that can turn an NP-problem. This paper presents a model of an aggressive, single-turn strategy as a combinatorial optimization problem, termed the FAB problem. Using mathematical modeling, we demonstrate its equivalence to a 0-1 Knapsack problem, establishing the FAB problem as NP-hard. Additionally, an Integer Linear Programming (ILP) formulation is proposed to tackle real-world instances of the problem. By establishing the computational hardness of optimizing even relatively simple strategies, our work highlights the combinatorial complexity of the game.

arXiv:2501.12282v1 Announce Type: new Abstract: This work shows new results on the complexity of games Jelly-No and Hanano with various constraints on the size of the board and number of colours. Hanano and Jelly-No are one-player, 2D side-view puzzle games with a dynamic board consisting of coloured, movable blocks disposed on platforms. These blocks can be moved by the player and are subject to gravity. Both games somehow vary in their gameplay, but the goal is always to move the coloured blocks in order to reach a specific configuration and make them interact with each other or with other elements of the game. In Jelly-No the goal is to merge all coloured blocks of a same colour, which also happens when they make contact. In Hanano the goal is to make all the coloured blocks bloom by making contact with flowers of the same colour. Jelly-No was proven by Chao Yang to be NP-Complete under the restriction that all movable blocks are the same colour and NP-Hard for more colours. Hanano was proven by Michael C. Chavrimootoo to be PSPACE-Complete under the restriction that all movable blocks are the same colour. However, the question whether Jelly-No for more than one colours is also PSPACE-complete or if it too stays in NP was left open. In this paper, we settle this question, proving that Jelly-No is PSPACE-Complete with an unbounded number of colours. We further show that, if we allow black jellies (that is, jellies that do not need to be merged), the game is PSPACE-complete even for one colour. We further show that one-colour Jelly-No and Hanano remain NP-Hard even if the width or the height of the board are small constants.

arXiv:2501.12293v1 Announce Type: new Abstract: In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that $ \delta d_0 > 2 $, corrects up to $ \alpha n $ errors for a Tanner code $ T(G, C_0) $, where $ G $ is a $ (c, d, \alpha, \delta) $-bipartite expander with $n$ left vertices, and $ C_0 \subseteq \mathbb{F}_2^d $ is a linear inner code with minimum distance $ d_0 $. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required $ \delta d_0 > 3 $. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of $ \alpha n $, compared with the previous radius of $ \frac{2\alpha}{d_0(1 + 0.5c\delta) }n$. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code $T(G,C_0)$ is approximately $f_\delta^{-1} \left( \frac{1}{d_0} \right) \alpha n $, where $ f_\delta(\cdot) $ is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from $\alpha n$ to approximately $f_\delta^{-1}(\frac{2}{d_0})\alpha n$.

arXiv:2501.12007v1 Announce Type: cross Abstract: We introduce a quantum analogue of classical first-order logic (FO) and develop a theory of quantum first-order logic as a basis of the productive discussions on the power of logical expressiveness toward quantum computing. The purpose of this work is to logically express "quantum computation" by introducing specially-featured quantum connectives and quantum quantifiers that quantify fixed-dimensional quantum states. Our approach is founded on the recently introduced recursion-theoretical schematic definitions of time-bounded quantum functions, which map finite-dimensional Hilbert spaces to themselves. The quantum first-order logic (QFO) in this work therefore looks quite different from the well-known old concept of quantum logic based on lattice theory. We demonstrate that quantum first-order logics possess an ability of expressing bounded-error quantum logarithmic-time computability by the use of new "functional" quantum variables. In contrast, an extra inclusion of quantum transitive closure operator helps us characterize quantum logarithmic-space computability. The same computability can be achieved by the use of different "functional" quantum variables.

arXiv:2407.08385v2 Announce Type: replace Abstract: Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let $h^d$ denote the standard $d$-fold composition of the base function $h$. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function $f:\{0,1\}^n\to \{0,1\}$ is a recursive function of the form $h^d$, with $h$ being any base function and $d= \Omega(\log\log n)$. (II) The inner function is a recursive function of the form $h^d$, with $h$ being any constant arity base function (other than AND and OR) and $d= \Omega(\log\log n)$, where $n$ is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.

arXiv:2206.05434v4 Announce Type: replace-cross Abstract: We define rewinding operators that invert quantum measurements. Then, we define complexity classes ${\sf RwBQP}$, ${\sf CBQP}$, and ${\sf AdPostBQP}$ as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that ${\sf BPP}^{\sf PP}\subseteq{\sf RwBQP}={\sf CBQP}={\sf AdPostBQP}\subseteq{\sf PSPACE}$. As a byproduct of this result, we show that any problem in ${\sf PostBQP}$ can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that ${\sf BQP}\nsupseteq{\sf SZK}$, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in ${\sf PP}$.

arXiv:2501.11192v1 Announce Type: new Abstract: We prove new parameterized complexity results for the FO Model Checking problem and in particular for Independent Set, for two recently introduced subclasses of $H$-graphs, namely proper $H$-graphs and non-crossing $H$-graphs. It is known that proper $H$-graphs, and thus $H$-graphs, may have unbounded twin-width. However, we prove that for every connected multigraph $H$ with no self-loops, non-crossing $H$-graphs have bounded proper mixed-thinness, and thus bounded twin-width. Consequently, we can apply a well-known result of Bonnet, Kim, Thomass\'e, and Watrigant (2021) to find that the FO Model Checking problem is in $\mathsf{FPT}$ for non-crossing $H$-graphs when parameterized by $\Vert H \Vert+\ell$, where $\Vert H \Vert$ is the size of $H$ and $\ell$ is the size of a formula. In particular, this implies that Independent Set is in $\mathsf{FPT}$ on non-crossing $H$-graphs when parameterized by $\Vert H \Vert+k$, where $k$ is the solution size. In contrast, Independent Set for general $H$-graphs is $\mathsf{W[1]}$-hard when parameterized by $\Vert H \Vert +k$. We strengthen the latter result by proving thatIndependent Set is $\mathsf{W[1]}$-hard even on proper $H$-graphs when parameterized by $\Vert H \Vert+k$. In this way, we solve, subject to $\mathsf{W[1]}\neq \mathsf{FPT}$, an open problem of Chaplick (2023), who asked whether there exist problems that can be solved faster for non-crossing $H$-graphs than for proper $H$-graphs.

arXiv:2501.12044v1 Announce Type: new Abstract: In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning Tree (EMST), and (iii) approximate DBSCAN. Our first result is a $O(1)$-round Las Vegas (i.e., succeeding with high probability) MPC algorithm for computing the connected components on a $d$-dimensional $c$-penetration grid graph ($(d,c)$-grid graph), where both $d$ and $c$ are positive integer constants. In such a grid graph, each vertex is a point with integer coordinates in $\mathbb{N}^d$, and an edge can only exist between two distinct vertices with $\ell_\infty$-norm at most $c$. To our knowledge, the current best existing result for computing the connected components (CC's) on $(d,c)$-grid graphs in the MPC model is to run the state-of-the-art MPC CC algorithms that are designed for general graphs: they achieve $O(\log \log n + \log D)$[FOCS19] and $O(\log \log n + \log \frac{1}{\lambda})$[PODC19] rounds, respectively, where $D$ is the {\em diameter} and $\lambda$ is the {\em spectral gap} of the graph. With our grid graph connectivity technique, our second main result is a $O(1)$-round Las Vegas MPC algorithm for computing approximate Euclidean MST. The existing state-of-the-art result on this problem is the $O(1)$-round MPC algorithm proposed by Andoni et al.[STOC14], which only guarantees an approximation on the overall weight in expectation. In contrast, our algorithm not only guarantees a deterministic overall weight approximation, but also achieves a deterministic edge-wise weight approximation.The latter property is crucial to many applications, such as finding the Bichromatic Closest Pair and DBSCAN clustering. Last but not the least, our third main result is a $O(1)$-round Las Vegas MPC algorithm for computing an approximate DBSCAN clustering in $O(1)$-dimensional space.

arXiv:2501.10688v1 Announce Type: new Abstract: Looped Transformers have shown exceptional capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple entities, enabling richer representations but introducing significant computational challenges. In this work, we extend the Loop Transformer architecture to simulate hypergraph algorithms efficiently, addressing the gap between neural networks and combinatorial optimization over hypergraphs. In this paper, we extend the Loop Transformer architecture to simulate hypergraph algorithms efficiently, addressing the gap between neural networks and combinatorial optimization over hypergraphs. Specifically, we propose a novel degradation mechanism for reducing hypergraphs to graph representations, enabling the simulation of graph-based algorithms, such as Dijkstra's shortest path. Furthermore, we introduce a hyperedge-aware encoding scheme to simulate hypergraph-specific algorithms, exemplified by Helly's algorithm. The paper establishes theoretical guarantees for these simulations, demonstrating the feasibility of processing high-dimensional and combinatorial data using Loop Transformers. This work highlights the potential of Transformers as general-purpose algorithmic solvers for structured data.

arXiv:2501.10633v1 Announce Type: new Abstract: We introduce the meta-problem Sidestep$(\Pi, \mathsf{dist}, d)$ for a problem $\Pi$, a metric $\mathsf{dist}$ over its inputs, and a map $d: \mathbb N \to \mathbb R_+ \cup \{\infty\}$. A solution to Sidestep$(\Pi, \mathsf{dist}, d)$ on an input $I$ of $\Pi$ is a pair $(J, \Pi(J))$ such that $\mathsf{dist}(I,J) \leqslant d(|I|)$ and $\Pi(J)$ is a correct answer to $\Pi$ on input $J$. This formalizes the notion of answering a related question (or sidestepping the question), for which we give some practical and theoretical motivations, and compare it to the neighboring concepts of smoothed analysis, planted problems, and edition problems. Informally, we call hardness radius the ``largest'' $d$ such that Sidestep$(\Pi, \mathsf{dist}, d)$ is NP-hard. This framework calls for establishing the hardness radius of problems $\Pi$ of interest for the relevant distances $\mathsf{dist}$. We exemplify it with graph problems and two distances $\mathsf{dist}_\Delta$ and $\mathsf{dist}_e$ (the edge edit distance) such that $\mathsf{dist}_\Delta(G,H)$ (resp. $\mathsf{dist}_e(G,H)$) is the maximum degree (resp. number of edges) of the symmetric difference of $G$ and $H$ if these graphs are on the same vertex set, and $+\infty$ otherwise. We show that the decision problems Independent Set, Clique, Vertex Cover, Coloring, Clique Cover have hardness radius $n^{\frac{1}{2}-o(1)}$ for $\mathsf{dist}_\Delta$, and $n^{\frac{4}{3}-o(1)}$ for $\mathsf{dist}_e$, that Hamiltonian Cycle has hardness radius 0 for $\mathsf{dist}_\Delta$, and somewhere between $n^{\frac{1}{2}-o(1)}$ and $n/3$ for $\mathsf{dist}_e$, and that Dominating Set has hardness radius $n^{1-o(1)}$ for $\mathsf{dist}_e$. We leave several open questions.

arXiv:2501.06427v1 Announce Type: cross Abstract: It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexity on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, Behrens-Arpino-Kivva-Zdeborov\'a and Minzer-Sah-Sawhney have recently conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree $D\leq o(N)$: any such algorithm has probability $o(1)$ to output a stable local optimum. To the best of our knowledge, this is the first result to prove that even constant-degree polynomials have probability $o(1)$ to solve a random search problem without planted structure. To prove this, we develop a general-purpose enhancement of the ensemble overlap gap property, and as a byproduct improve previous results on spin glass optimization, maximum independent set, random $k$-SAT, and the Ising perceptron to strong low degree hardness. Finally for spherical spin glasses with no external field, we prove that Langevin dynamics does not find stable local optima within dimension-free time.

arXiv:2501.07413v1 Announce Type: cross Abstract: We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lov{\'a}sz--Schrijver SDP operator $\text{LS}_+$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\ell$, the smallest possible graph with $\text{LS}_+$-rank $\ell$ contains $3\ell$ vertices. This result is sharp and settles a conjecture posed by Lipt{\'a}k and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\ell$ there exists a vertex-transitive graph on $4\ell+12$ vertices with $\text{LS}_+$-rank at least $\ell$.

arXiv:2501.07529v1 Announce Type: new Abstract: The mutational heterogeneity of tumours can be described with a tree representing the evolutionary history of the tumour. With noisy sequencing data there may be uncertainty in the inferred tree structure, while we may also wish to study patterns in the evolution of cancers in different patients. In such situations, understanding tree similarities is a key challenge, and therefore we present an approach to determine distances between trees. Considering the bounded height of trees, we determine the distances associated with the swap operations over strings. While in general, by solving the {\sc Maximum Common Almost $v$-tree} problem between two trees, we describe an efficient approach to determine the minimum number of operations to transform one tree into another. The inherent noise in current statistical methods for constructing mutation evolution trees of cancer cells presents a significant challenge: handling such collections of trees to determine a consensus tree that accurately represents the set and evaluating the extent of their variability or dispersion. Given a set of mutation trees and the notion of distance, there are at least two natural ways to define the ``target'' tree, such as a min-sum (\emph{median tree}) or a min-max (\emph{closest tree}) of a set of trees. Thus, considering a set of trees as input and dealing with the {\sc median} and {\sc closest} problems, we prove that both problems are \NP-complete, even with only three input trees. In addition, we develop algorithms to obtain upper bounds on the median and closest solutions, which are analysed by the experiments presented on generated and on real databases. We show a fast way to find consensus trees with better results than any tree in the input set while still preserving all internal structure.

arXiv:2411.10719v3 Announce Type: replace Abstract: The Seat Arrangement Problem is a problem of finding a desirable seat arrangement for given preferences of agents and a seat graph that represents a configuration of seats. In this paper, we consider decision problems of determining if an envy-free arrangement exists and an exchange-stable arrangement exists, when a seat graph is an $\ell \times m$ grid graph. When $\ell=1$, the seat graph is a path of length $m$ and both problems have been known to be NP-complete. In this paper, we extend it and show that both problems are NP-complete for any integer $\ell \geq 2$.

arXiv:2410.13470v2 Announce Type: replace Abstract: The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes have played an influential role in coding theory and complexity theory. This is especially so in the setting of $U$ being ${\mathbb{F}}_q$ where they possess deep locality properties. However, these Reed-Muller codes have a significant limitation in terms of the rate achievable -- the rate cannot be more than $\frac{1}{m{!}} = \exp(-m \log m)$. In this work, we give the first constructions of multivariate polynomial evaluation codes which overcome the rate limitation -- concretely, we give explicit evaluation domains $S \subseteq \mathbb{F}_q^m$ on which evaluating $m$-variate polynomials of degree at most $d$ gives a good code. For $m= O(1)$, these new codes have relative distance $\Omega(1)$ and rate $1 - \epsilon$ for any $\epsilon > 0$. In fact, we give two quite different constructions, and for both we develop efficient decoding algorithms for these codes that can decode from half the minimum distance. The first of these codes is based on evaluating multivariate polynomials on simplex-like sets whereas the second construction is more algebraic, and surprisingly (to us), has some strong locality properties, specifically, we show that they are locally testable.

arXiv:2412.06189v3 Announce Type: replace Abstract: One fundamental question in database theory is the following: Given a Boolean conjunctive query Q, what is the best complexity for computing the answer to Q in terms of the input database size N? When restricted to the class of combinatorial algorithms, it is known that the best known complexity for any query Q is captured by the submodular width of Q. However, beyond combinatorial algorithms, certain queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queries Q. In this work, we introduce a general framework that captures the best complexity for answering any Boolean conjunctive query Q using matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the notion of submodular width to a new stronger notion called the omega-submodular width that naturally incorporates the power of fast matrix multiplication. We describe a matching algorithm that computes the answer to any query Q in time corresponding to the omega-submodular width of Q. We show that our framework recovers the best known complexities for Boolean queries that have been studied in the literature, to the best of our knowledge, and also discovers new algorithms for some classes of queries that improve upon the best known complexities.