Search

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid =_3 \right)$, where $f$ is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of $f$. The constraint function can take both positive and negative values, allowing for cancellations. The dichotomy extends easily to rational valued functions of the same type. In addition, we discover a new phenomenon: there is a set $\mathcal{F}$ with the property that for every $f \in \mathcal{F}$ the problem $\operatorname{Holant}\left(f\mid =_3 \right)$ is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by $\left[\begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix}\right]$ to FKT together with an independent global argument., Accepted by FCT 2021

A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its complement is $k^{\widetilde{\Omega}(\log k)}$. Equivalently, the ones in the matrix can be partitioned into $k$ combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is $k^{\widetilde{\Omega}(\log k)}$. This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, G\"{o}\"{o}s, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers $k$, there exists a regular graph with biclique partition number $k$ and chromatic number $k^{\widetilde{\Omega}(\log k)}$., Comment: 21 pages

We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < ��, �� < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most �� N has at least (1-��)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {�� N}/{2 ��}. This is strictly better than the best known previous result of 2(1-��) �� N [Madhu Sudan, 2000; Viderman, 2013] whenever �� < 1/2, and improves the previous result significantly when �� is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever �� < 1/4. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 43:1-43:3

The Covering Salesman Problem (CSP) is a generalization of the Traveling Salesman Problem in which the tour is not required to visit all vertices, as long as all vertices are covered by the tour. The objective of CSP is to find a minimum length Hamiltonian cycle over a subset of vertices that covers an undirected graph. In this paper, valid inequalities from the generalized traveling salesman problem are applied to the CSP in addition to new valid inequalities that explore distinct aspects of the problem. A branch-and-cut framework assembles exact and heuristic separation routines for integer and fractional CSP solutions. Computational experiments show that the proposed framework outperformed methodologies from literature with respect to optimality gaps. Moreover, optimal solutions were proven for several previously unsolved instances.

The Maximum Likelihood Decoding Problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the Multivariate Quadratic System Problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families., Accepted for publication in Annali di Matematica Pura ed Applicata (1923 -)

Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin’s NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the $-Calculus, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in $-calculus.

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix.

We establish primitive recursive (PR) versions of some known facts about computable ordered fields of reals and computable reals, and apply them to prove primitive recursiveness of several important problems in linear algebra and analysis. One of the central results of this paper is a partial PR analogue of Ershov–Madison’s theorem about real closures of computable ordered fields. It allows us, in particular, to obtain PR root-finding algorithms in the PR real and algebraic closures of PR fields with a certain property (PR splitting). We also relate the corresponding fields to the PR reals, as well as introduce and study the notion of a PR metric space. It enables us to derive sufficient conditions for PR computing of normal forms of matrices and solution operators of symmetric hyperbolic systems of PDEs. The methods represent a mix of symbolic and approximate algorithms.

Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation. Indeed, Jozsa conjectured that “ Any quantum polynomial-time algorithm can be implemented with only O (log n ) quantum depth interspersed with polynomial-time classical computations. ” This can be formalized as asserting the equivalence of BQP and “ BQNC BPP .” However, Aaronson conjectured that “ there exists an oracle separation between BQP and BPP BQNC . ” BQNC BPP and BPP BQNC are two natural and seemingly incomparable ways of hybrid classical-quantum computation. In this work, we manage to prove Aaronson’s conjecture and in the meantime prove that Jozsa’s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter d , there exists an oracle that separates quantum depth d and 2 d +1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth does make the hybrid model more powerful, and this cannot be traded by classical computation.

As the primary cause of software defects, human error is the key to understanding, and perhaps to predicting and avoiding them. Little research has been done to predict defects on the basis of the cognitive errors that cause them. This paper proposes an approach to predicting software defects through knowledge about the cognitive mechanisms of human errors. Our theory is that the main process behind a software defect is that an error-prone scenario triggers human error modes, which psychologists have observed to recur across diverse activities. Software defects can then be predicted by identifying such scenarios, guided by this knowledge of typical error modes. The proposed idea emphasizes predicting the exact location and form of a possible defect. We conducted two case studies to demonstrate and validate this approach, with 55 programmers in a programming competition and 5 analysts serving as the users of the approach. We found it impressive that the approach was able to predict, at the requirement phase, the exact locations and forms of 7 out of the 22 (31.8%) specific types of defects that were found in the code. The defects predicted tended to be common defects: their occurrences constituted 75.7% of the total number of defects in the 55 developed programs; each of them was introduced by at least two persons. The fraction of the defects introduced by a programmer that were predicted was on average (over all programmers) 75%. Furthermore, these predicted defects were highly persistent through the debugging process. If the prediction had been used to successfully prevent these defects, this could have saved 46.2% of the debugging iterations. This excellent capability of forecasting the exact locations and forms of possible defects at the early phases of software development recommends the approach for substantial benefits to defect prevention and early detection., 30 pages, 5 figures, and 17 tables

In this work, we demonstrate the offline FPGA realization of both recurrent and feedforward neural network (NN)-based equalizers for nonlinearity compensation in coherent optical transmission systems. First, we present a realization pipeline showing the conversion of the models from Python libraries to the FPGA chip synthesis and implementation. Then, we review the main alternatives for the hardware implementation of nonlinear activation functions. The main results are divided into three parts: a performance comparison, an analysis of how activation functions are implemented, and a report on the complexity of the hardware. The performance in Q-factor is presented for the cases of bidirectional long-short-term memory coupled with convolutional NN (biLSTM + CNN) equalizer, CNN equalizer, and standard 1-StpS digital back-propagation (DBP) for the simulation and experiment propagation of a single channel dual-polarization (SC-DP) 16QAM at 34 GBd along 17x70km of LEAF. The biLSTM+CNN equalizer provides a similar result to DBP and a 1.7 dB Q-factor gain compared with the chromatic dispersion compensation baseline in the experimental dataset. After that, we assess the Q-factor and the impact of hardware utilization when approximating the activation functions of NN using Taylor series, piecewise linear, and look-up table (LUT) approximations. We also show how to mitigate the approximation errors with extra training and provide some insights into possible gradient problems in the LUT approximation. Finally, to evaluate the complexity of hardware implementation to achieve 200G and 400G throughput, fixed-point NN-based equalizers with approximated activation functions are developed and implemented in an FPGA., Comment: Invited paper at Journal of Lightwave Technology - IEEE

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO., 46 pages, 5 figures, 15 tables

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $\epsilon$-spectral sparsifier in sublinear time $\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for $k$-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut., Comment: v2: several small improvements to the text. An extended abstract will appear in FOCS'20; v3: corrected a minor mistake in Appendix A; v4: final version as published in SICOMP

We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal graph if and only if it is stable and has at most factorial speed. Our counter-example follows from the existence of a sequence of $n \times n$ Boolean matrices $M_n$, such that their public-coin randomized communication complexity tends to infinity, while the randomized communication complexity of every $\sqrt{n}\times \sqrt{n}$ submatrix of $M_n$ is bounded by a universal constant., Comment: 7 pages

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\text{Quasi-NP} = \text{NTIME}[n^{(\log n)^{O(1)}}]$ and $\text{NEXP}$ do not have small circuits from various circuit classes ${\cal C}$, by showing that ${\cal C}$ admits non-trivial satisfiability and/or $\#$SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of non-trivial $\#$SAT algorithm for a circuit class ${\mathcal C}$. Say a symmetric Boolean function $f(x_1,\ldots,x_n)$ is sparse if it outputs $1$ on $O(1)$ values of $\sum_i x_i$. We show that for every sparse $f$, and for all "typical" ${\cal C}$, faster $\#$SAT algorithms for ${\cal C}$ circuits actually imply lower bounds against the circuit class $f \circ {\cal C}$, which may be stronger than ${\cal C}$ itself. In particular: $\#$SAT algorithms for $n^k$-size ${\cal C}$-circuits running in $2^n/n^k$ time (for all $k$) imply $\text{NEXP}$ does not have $f \circ {\cal C}$-circuits of polynomial size. $\#$SAT algorithms for $2^{n^{\epsilon}}$-size ${\cal C}$-circuits running in $2^{n-n^{\epsilon}}$ time (for some $\epsilon > 0$) imply $\text{Quasi-NP}$ does not have $f \circ {\cal C}$-circuits of polynomial size. Applying $\#$SAT algorithms from the literature, one immediate corollary of our results is that $\text{Quasi-NP}$ does not have $\text{EMAJ} \circ \text{ACC}^0 \circ \text{THR}$ circuits of polynomial size, where $\text{EMAJ}$ is the "exact majority" function, improving previous lower bounds against $\text{ACC}^0$ [Williams JACM'14] and $\text{ACC}^0 \circ \text{THR}$ [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class., Comment: To appear in STACS 2020

The constraint satisfaction problem (CSP) is a computational problem that includes a range of important problems in computer science. We point out that fundamental concepts of the CSP, such as the solution set of an instance and polymorphisms, can be formulated abstractly inside the 2-category PFinSet of finite sets and sets of functions between them. The 2-category PFinSet is a quantaloid, and the formulation relies mainly on structure available in any quantaloid. This observation suggests a formal development of generalisations of the CSP and concomitant notions of polymorphism in a large class of quantaloids. We extract a class of optimisation problems as a special case, and show that their computational complexity can be classified by the associated notion of polymorphism., In Proceedings ACT 2021, arXiv:2211.01102

An $(n,r,h,a,q)$-Local Reconstruction Code (LRC) is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$' local parity checks to recover from `$a$' erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience -- namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to `$a$' erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$-MR LRCs with field size $q$ bounded by $\left(O\left(\max\{r,n/r\}\right)\right)^{\min\{h,r-a\}}$. This improves upon known constructions in many relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta(\sqrt{n})$, $r-a=\Theta(\sqrt{n})$ and $h$ is a fixed constant with $h\le a+2$, achieving the optimal field size of $\Theta_{h}(n^{h/2}).$ Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory.

The point of building a quantum computer is that it allows to model living things with predictive power and gives the opportunity to control life. Its scaling means not just the improvement of the instrument part, but also, mainly, mathematical and software tools, and our understanding of the QC problem. The first principle of quantum modeling is the reduction of reality to finite-dimensional models similar to QED in optical cavities. The second principle is a strict limitation of the so-called Feynman principle, the number of qubits in the standard formulation of the QC. This means treating decoherence exclusively as a limitation of the memory of a classical modeling computer, and introducing corresponding progressive restrictions on the working area of the Hilbert space of quantum states as the model expands. The third principle is similarity in processes of different nature. The quantum nature of reality is manifested in this principle; its nature is quantum nonlocality, which is the main property that ensures the prospects of quantum physical devices and their radical advantage over classical ones., 10 pages, 1 figure, Latex

For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$. We prove the same dichotomy for graphs of bounded radius. For a graph $H$, a graph is $H$-free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$-free graphs, extending a recent result of Feghali for $P_5$-free graphs. We then extend our result to hold even for $(sP_3+P_6)$-free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$-free graphs.

Consider an information diffusion process on a graph $G$ that starts with $k>0$ burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as $k$ other unburnt vertices. The \emph{$k$-burning number} of $G$ is the minimum number of steps $b_k(G)$ such that all the vertices can be burned within $b_k(G)$ steps. Note that the last step may have smaller than $k$ unburnt vertices available, where all of them are burned. The $1$-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to $k$-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor $k$. In this paper we prove that computing $k$-burning number is APX-hard, for any fixed constant $k$. We then give an $O((n+m)\log n)$-time 3-approximation algorithm for computing $k$-burning number, for any $k\ge 1$, where $n$ and $m$ are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.

With the rapid popularization of big data, the dichotomy between tractable and intractable problems in big data computing has been shifted. Sublinear time, rather than polynomial time, has recently been regarded as the new standard of tractability in big data computing. This change brings the demand for new methodologies in computational complexity theory in the context of big data. Based on the prior work for sublinear-time complexity classes \cite{DBLP:journals/tcs/GaoLML20}, this paper focuses on sublinear-time reductions specialized for problems in big data computing. First, the pseudo-sublinear-time reduction is proposed and the complexity classes \Pproblem and \PsT are proved to be closed under it. To establish \PsT-intractability for certain problems in \Pproblem, we find the first problem in $\Pproblem \setminus \PsT$. Using the pseudo-sublinear-time reduction, we prove that the nearest edge query is in \PsT but the algebraic equation root problem is not. Then, the pseudo-polylog-time reduction is introduced and the complexity class \PsPL is proved to be closed under it. The \PsT-completeness under it is regarded as an evidence that some problems can not be solved in polylogarithmic time after a polynomial-time preprocessing, unless \PsT = \PsPL. We prove that all \PsT-complete problems are also \Pproblem-complete, which gives a further direction for identifying \PsT-complete problems.

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set called universe and an infinite set of two-valued functions (attributes) defined on the universe. We consider the notion of a problem over information system, which is described by a finite number of attributes and a mapping associating a decision to each tuple of attribute values. As algorithms for problem solving, we use deterministic and nondeterministic decision trees. As time and space complexity, we study the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either almost as logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into five complexity classes, and study for each class issues related to time-space trade-off for decision trees.

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs~$G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i,-i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert > 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model., Comment: 49 pages, 9 figures On last update: we fixed some typos and updated the references

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as {\it circle graphs}, {\it $k$-polygon-circle graphs}, {\it circle-trapezoid graphs}, {\it trapezoid graphs}. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing {\it trapezoid} graphs and give a succinct navigational oracle for this class of graphs.

We prove that functions over the reals computable in polynomial time can be characterised using discrete ordinary differential equations (ODE), also known as finite differences. We also provide a characterisation of functions computable in polynomial space over the reals. In particular, this covers space complexity, while existing characterisations were only able to cover time complexity, and were restricted to functions over the integers. We prove furthermore that no artificial sign or test function is needed even for time complexity. At a technical level, this is obtained by proving that Turing machines can be simulated with analytic discrete ordinary differential equations. We believe this result opens the way to many applications, as it opens the possibility of programming with ODEs, with an underlying well-understood time and space complexity., arXiv admin note: text overlap with arXiv:2209.13404

It is important to study how strategic agents can affect the outcome of an election. There has been a long line of research in the computational study of elections on the complexity of manipulative actions such as manipulation and bribery. These problems model scenarios such as voters casting strategic votes and agents campaigning for voters to change their votes to make a desired candidate win. A common assumption is that the preferences of the voters follow the structure of a domain restriction such as single peakedness, and so manipulators only consider votes that also satisfy this restriction. We introduce the model where the preferences of the voters define their own restriction and strategic actions must ``conform'' by using only these votes. In this model, the election after manipulation will retain common domain restrictions. We explore the computational complexity of conformant manipulative actions and we discuss how conformant manipulative actions relate to other manipulative actions., A version of this paper will appear in the Proceedings of FCT 2023

Sample reweighting is one of the most widely used methods for correcting the error of least squares learning algorithms in reproducing kernel Hilbert spaces (RKHS), that is caused by future data distributions that are different from the training data distribution. In practical situations, the sample weights are determined by values of the estimated Radon-Nikod\'ym derivative, of the future data distribution w.r.t.~the training data distribution. In this work, we review known error bounds for reweighted kernel regression in RKHS and obtain, by combination, novel results. We show under weak smoothness conditions, that the amount of samples, needed to achieve the same order of accuracy as in the standard supervised learning without differences in data distributions, is smaller than proven by state-of-the-art analyses.

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has an (information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to the verifier. The verifier has a read-once one-way access to that proof and is able to verify that the computation was performed correctly. That is, if the input is in the language and the prover is honest, the verifier accepts with high probability, and, if the input is not in the language, the verifier rejects with high probability even if the prover is adversarial. Moreover, the verifier uses only $O(\log n)$ random bits.

Given a graph $G = (V, E)$, a non-empty set $S \subseteq V$ is a defensive alliance, if for every vertex $v \in S$, the majority of its closed neighbours are in $S$, that is, $|N_G[v] \cap S| \geq |N_G[v] \setminus S|$. The decision version of the problem is known to be NP-Complete even when restricted to split and bipartite graphs. The problem is \textit{fixed-parameter tractable} for the parameters solution size, vertex cover number and neighbourhood diversity. For the parameters treewidth and feedback vertex set number, the problem is W[1]-hard. \\ \hspace*{2em} In this paper, we study the defensive alliance problem for graphs with bounded degree. We show that the problem is \textit{polynomial-time solvable} on graphs with maximum degree at most 5 and NP-Complete on graphs with maximum degree 6. This rules out the fixed-parameter tractability of the problem for the parameter maximum degree of the graph. We also consider the problem from the standpoint of parameterized complexity. We provide an FPT algorithm using the Integer Linear Programming approach for the parameter distance to clique. We also answer an open question posed in \cite{AG2} by providing an FPT algorithm for the parameter twin cover., 20 pages

We extend the pseudorandomness of random walks on expander graphs using the sticky random walk. Building on prior works, it was recently shown that expander random walks can fool all symmetric functions in total variation distance (TVD) upto an $O(\lambda(\frac{p}{\min f})^{O(p)})$ error, where $\lambda$ is the second largest eigenvalue of the expander, $p$ is the size of the arbitrary alphabet used to label the vertices, and $\min f = \min_{b\in[p]} f_b$, where $f_b$ is the fraction of vertices labeled $b$ in the graph. Golowich and Vadhan conjecture that the dependency on the $(\frac{p}{\min f})^{O(p)}$ term is not tight. In this paper, we resolve the conjecture in the affirmative for a family of expanders. We present a generalization of the sticky random walk for which Golowich and Vadhan predict a TVD upper bound of $O(\lambda p^{O(p)})$ using a Fourier-analytic approach. For this family of graphs, we use a combinatorial approach involving the Krawtchouk functions to derive a strengthened TVD of $O(\lambda)$. Furthermore, we present equivalencies between the generalized sticky random walk, and, using linear-algebraic techniques, show that the generalized sticky random walk parameterizes an infinite family of expander graphs., Comment: 21 pages, 2 figures

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou FOCS'2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent $\omega$, but also improves the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia SODA'2018]. In particular, the new bound on $\omega$ is $\omega \le 2.371552$ (improved from $\omega \le 2.371866$). For the dual matrix multiplication exponent $\alpha$ defined as the largest $\alpha$ for which $\omega(1, \alpha, 1) = 2$, we obtain the improvement $\alpha \ge 0.321334$ (improved from $\alpha \ge 0.31389$). Similar improvements are obtained for various other exponents for multiplying rectangular matrices., Comment: 54 pages

Treewidth is as an important parameter that yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and QUANTIFIED SAT or, more generally, QUANTIFIED CSP, are fixed-parameter tractable parameterized by the treewidth of the input's (primal) graph plus the length of the MSO-formula [Courcelle, Information & Computation 1990] and the quantifier rank [Chen, ECAI 2004], respectively. The algorithms generated by these (meta-)results have running times whose dependence on treewidth is a tower of exponents. A conditional lower bound by Fichte et al. [LICS 2020] shows that, for QUANTIFIED SAT, the height of this tower is equal to the number of quantifier alternations. Lower bounds showing that at least double-exponential factors in the running time are necessary, exhibit the extraordinary computational hardness of such problems, and are rare: there are very few (for treewidth tw and vertex cover vc parameterizations) and they are for $\Sigma_2^p$-, $\Sigma_3^p$- or #NP-complete problems. We show, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to obtain such lower bounds. Specifically, for the well-studied NP-complete metric graph problems METRIC DIMENSION, STRONG METRIC DIMENSION, and GEODETIC SET, we prove that they do not admit $2^{2^{o(tw)}} \cdot n^{O(1)}$-time algorithms, even on bounded diameter graphs, unless the ETH fails. For STRONG METRIC DIMENSION, this lower bound holds even for vc. This is impossible for the other two as they admit $2^{O({vc}^2)} \cdot n^{O(1)}$-time algorithms. We show that, unless the ETH fails, they do not admit $2^{o({vc}^2)}\cdot n^{O(1)}$-time algorithms, thereby adding to the short list of problems admitting such lower bounds. The latter results also yield lower bounds on the vertex-kernel sizes. We complement all our lower bounds with matching upper bounds.

We study the problem of reconfiguring one minimum $s$-$t$-separator $A$ into another minimum $s$-$t$-separator $B$ in some $n$-vertex graph $G$ containing two non-adjacent vertices $s$ and $t$. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming $A$ into $B$. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most $\ell$ jumps can transform $A$ into $B$ is an $\textsf{NP}$-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size $k$ of the minimum \stseps and when parameterized by the number of jumps $\ell$. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless $\textsf{NP} \subseteq \textsf{coNP/poly}$. We complete the picture by designing a kernel with $\mathcal{O}(\ell^2)$ vertices and edges for the length $\ell$ of the sequence as a parameter., 37 pages, 9 figures

This paper addresses the computational problem of deciding invertibility (or one to one-ness) of a Boolean map $F$ in $n$-Boolean variables. This problem has a special case of deciding invertibilty of a map $F:\mathbb{F}_{2}^n\rightarrow\mathbb{F}_{2}^n$ over the binary field $\mathbb{F}_2$. Further the problem can be extended and stated over a finite field $\mathbb{F}$ instead of $\mathbb{F}_2$. Algebraic condition for invertibility of $F$ in this special case over a finite field is well known to be equivalent to invertibility of the Koopman operator of $F$ as shown in \cite{RamSule}. In this paper a condition for invertibility is derived in the special case of Boolean maps $F:B_0^n\rightarrow B_0^n$ where $B_0$ is the two element Boolean algebra in terms of \emph{implicants} of Boolean equations. This condition is then extended to the case of general maps in $n$ variables. Hence this condition answers the special case of invertibility of the map $F$ defined over the binary field $\mathbb{F}_2$ alternatively, in terms of implicants instead of the Koopman operator. The problem of deciding invertibility of a map $F$ (or that of finding its $GOE$) over finite fields appears to be distinct from the satisfiability problem (SAT) or the problem of deciding consistency of polynomial equations over finite fields. Hence the well known algorithms for deciding SAT or of solvability using Grobner basis for checking membership in an ideal generated by polynomials is not known to answer the question of invertibility of a map. Similarly it appears that algorithms for satisfiability or polynomial solvability are not useful for computation of $GOE(F)$ even for maps over the binary field $\mathbb{F}_2$., 15 pages

Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation trade-off that is quite close to the upper bounds. In \emph{directed} graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since $d(u,v)$ may not be the same as $d(v,u)$, there are multiple ways to define the problem, the two most natural being the \emph{(one-way) diameter} ($\max_{(u,v)} d(u,v)$) and the \emph{roundtrip diameter} ($\max_{u,v} d(u,v)+d(v,u)$). In this paper we make progress on the outstanding open question for each of them. -- We design the first algorithm for diameter in sparse directed graphs to achieve $n^{1.5-\varepsilon}$ time with an approximation factor better than $2$. The new upper bound trade-off makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication. -- We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a $1.5$-approximation in subquadratic time would refute the All-Nodes $k$-Cycle hypothesis, and any $(2-\varepsilon)$-approximation would imply a breakthrough algorithm for approximate $\ell_{\infty}$-Closest-Pair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.

We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that produce a data structure for the solution $x\in\mathbb{R}^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\|x-A^{+}b\|\leq\epsilon\|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$ in the general case, where $\kappa_{F} =\|A\|_F\|A^+\|$ and $\kappa=\|A\|\|A^+\|$ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s \kappa\log(1/\epsilon))$, matching the quantum lower bound for solving linear systems in $\kappa$ and $1/\epsilon$ up to poly-logarithmic factors [Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$. Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims., Comment: 49 pages, 13 figures, 7 tables

Given a set of squares and a strip of bounded width and infinite height, we consider a square strip packaging problem, which we call the square independent packing problem (SIPP), to minimize the strip height so that all the squares are packed into independent cells separated by horizontal and vertical partitions. For the SIPP, we first investigate efficient solution representations and propose a compact representation that reduces the search space from $\Omega(n!)$ to $O(2^n)$, with $n$ the number of given squares, while guaranteeing that there exists a solution representation that corresponds to an optimal solution. Based on the solution representation, we show that the problem is NP-hard, and then we propose a fully polynomial-time approximation scheme (FPTAS) to solve it. We also propose three mathematical programming formulations based on different solution representations and confirm the performance of these algorithms through computational experiments. Finally, we discuss several extensions that are relevant to practical applications., Comment: 15 pages

We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbours are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs., This is an extended and revised version of a preliminary conference report that was presented in WAW 2023

We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show that these puzzles are efficiently verifiable, which remains an open question for general SUSPs. We also show that individual simplifiable SUSPs can achieve the same strength of bounds on the matrix multiplication exponent $\omega$ that infinite families of SUSPs can. We report on the construction, by computer search, of larger SUSPs than previously known for small width. This, combined with our tighter analysis, strengthens the upper bound on the matrix multiplication exponent from $2.66$ to $2.505$ obtainable via this computational approach, and nears the results of the handcrafted constructions of Cohn et al., Comment: 21 pages, 1 figure, 1 table

A graph $G$ is \emph{locally irregular} if no two of its adjacent vertices have the same degree. In [Fioravantes et al. Complexity of finding maximum locally irregular induced subgraph. {\it SWAT}, 2022], the authors introduced and studied the problem of finding a locally irregular induced subgraph of a given a graph $G$ of maximum order, or, equivalently, computing a subset $S$ of $V(G)$ of minimum order, whose deletion from $G$ results in a locally irregular graph; $S$ is denoted as an \emph{optimal vertex-irregulator of $G$}. In this work we provide an in-depth analysis of the parameterised complexity of computing an optimal vertex-irregulator of a given graph $G$. Moreover, we introduce and study a variation of this problem, where $S$ is a substet of the edges of $G$; in this case, $S$ is denoted as an \emph{optimal edge-irregulator of $G$}. In particular, we prove that computing an optimal vertex-irregulator of a graph $G$ is in FPT when parameterised by the vertex integrity, neighborhood diversity or cluster deletion number of $G$, while it is $W[1]$-hard when parameterised by the feedback vertex set number or the treedepth of $G$. In the case of computing an optimal edge-irregulator of a graph $G$, we prove that this problem is in FPT when parameterised by the vertex integrity of $G$, while it is NP-hard even if $G$ is a planar bipartite graph of maximum degree $4$, and $W[1]$-hard when parameterised by the size of the solution, the feedback vertex set or the treedepth of $G$. Our results paint a comprehensive picture of the tractability of both problems studied here, considering most of the standard graph-structural parameters.

For any Boolean functions $f$ and $g$, the question whether $R(f\circ g) = \tilde{\Theta}(R(f)R(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{deg}(f\circ g) = \tilde{\Theta}(\widetilde{deg}(f)\cdot\widetilde{deg}(g))$. These questions are two of the most important and well-studied problems, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function $f$ (or inner function $g$). This paper extends the class of outer functions for which $\text{R}$ and $\widetilde{\text{deg}}$ compose. A recent landmark result (Ben-David and Blais, 2020) showed that $R(f \circ g) = \Omega(noisyR(f)\cdot R(g))$. This implies that composition holds whenever $noisyR(f) = \Tilde{\Theta}(R(f))$. We show two results: (1)When $R(f) = \Theta(n)$, then $noisyR(f) = \Theta(R(f))$. (2) If $\text{R}$ composes with respect to an outer function, then $\text{noisyR}$ also composes with respect to the same outer function. On the other hand, no result of the type $\widetilde{deg}(f \circ g) = \Omega(M(f) \cdot \widetilde{deg}(g))$ (for some non-trivial complexity measure $M(\cdot)$) was known to the best of our knowledge. We prove that $\widetilde{deg}(f\circ g) = \widetilde{\Omega}(\sqrt{bs(f)} \cdot \widetilde{deg}(g)),$ where $bs(f)$ is the block sensitivity of $f$. This implies that $\widetilde{\text{deg}}$ composes when $\widetilde{\text{deg}}(f)$ is asymptotically equal to $\sqrt{\text{bs}(f)}$. It is already known that both $\text{R}$ and $\widetilde{\text{deg}}$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.

The Chinese Remainder Theorem for the integers says that every system of congruence equations is solvable as long as the system satisfies an obvious necessary condition. This statement can be generalized in a natural way to arbitrary algebraic structures using the language of Universal Algebra. In this context, an algebra is a structure of a first-order language with no relation symbols, and a congruence on an algebra is an equivalence relation on its base set compatible with its fundamental operations. A tuple of congruences of an algebra is called a Chinese Remainder tuple if every system involving them is solvable. In this article we study the complexity of deciding whether a tuple of congruences of a finite algebra is a Chinese Remainder tuple. This problem, which we denote CRT, is easily seen to lie in coNP. We prove that it is actually coNP-complete and also show that it is tractable when restricted to several well-known classes of algebras, such as vector spaces and distributive lattices. The polynomial algorithms we exhibit are made possible by purely algebraic characterizations of Chinese Remainder tuples for algebras in these classes, which constitute interesting results in their own right. Among these, an elegant characterization of Chinese Remainder tuples of finite distributive lattices stands out. Finally, we address the restriction of CRT to an arbitrary equational class $\mathcal{V}$ generated by a two-element algebra. Here we establish an (almost) dichotomy by showing that, unless $\mathcal{V}$ is the class of semilattices, the problem is either coNP-complete or tractable.

We introduce a just-in-time runtime program transformation based on repeated recursion unfolding. Our online polyvariant program specialization generates several versions of a recursion differentiated by the minimal number of recursive steps covered. The base case of the recursion is ignored in our technique. Our method is presented here on the basis of linear direct recursive rules. When a recursive call is encountered at runtime, first an unfolder creates specializations of the associated recursive rule on-the-fly and then an interpreter applies these rules to the call. Our approach reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of unfolded rules. Each rule is applied at most once. We prove correctness of our technique and determine its worst-case time complexity. For recursions that solve tractable problems and which have enough unfoldings that can sufficiently simplified, we prove a super-linear speedup theorem, i.e. speedup by more than a constant factor. The simplification is problem-specific and has to be provided at compile-time. In the best case, the complexity of the given recursion is reduced to that of its first recursive step. We have implemented the necessary unfolder and meta-interpreter for runtime repeated recursion unfolding in Constraint Handling Rules (CHR) with just five rules. We illustrate the feasibility of our approach with complexity results and benchmarks for several classical algorithms. The runtime improvement quickly reaches several orders of magnitude., Submitted to Journal Fundamenta Informaticae

We consider the Robber Locating Game, where an invisible moving robber tries to evade the pursuit of one or more helicopter cops, who send distance probes from anywhere on the graph. In this paper, we attempt to propose two useful constructions for general problems in this game: a state variable that describes the available game information for the cops, and a Cop Strategy Graph construction that presents all possibilities of the game given a deterministic cop strategy. Then we will use them, along with algorithms and pseudo-code, to explain the relationship between two graph parameters, the localization number and the subdivision number. Researchers have shown that the later has a linear relationship with the former, while the other direction does not. We will revisit their proofs, consolidate the essential correspondence between the two numbers via our proposed constructions, and show an explicit result for the non-linear relationship.

It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth-$r$ minors have constant density. More precisely, the formulas are $\exists x_1 ... x_k \#y \varphi(x_1,...,x_k, y)>N$, where $\varphi$ is an FO-formula. If $\varphi$ is quantifier-free, we can extend this result to nowhere dense graph classes with an almost linear FPT run time. Lifting this result further to slightly more general graph classes, namely almost nowhere dense classes, where the size of depth-$r$ clique minors is subpolynomial, is impossible unless FPT=W[1]. On the other hand, in almost nowhere dense classes we can approximate such counting formulas with a small additive error. Note those counting formulas are contained in FOC({

Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count $x \in \mathbb{N}$ with probability $1$ is asymptotically equal to a ``space-aware'' version of the Kolmogorov complexity of $x$, defined as $\mathrm{\widetilde{K}s}(x) = \min_p\left\{\lvert p \rvert / \log \lvert p \rvert + \log(\texttt{space}(\mathcal{U}(p))) : \mathcal{U}(p) = x \right\}$, where $p$ is a program for universal Turing machine $\mathcal{U}$. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating $x$, but also the space usage of that program. Probability $1$ computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they ``know when they are done'' in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any $b$ bits of information via $O(b/\log{b})$ reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded -- in the sense of generating precise molecular counts of species as the desired state.

Holonomic equations are recursive equations which allow computingefficiently numbers of combinatoric objects. R{\'e}my showed that theholonomic equation associated with binary trees yields an efficientlinear random generator of binary trees. I extend this paradigm toMotzkin trees and Schr{\"o}der trees and show that despite slightdifferences my algorithm that generates random Schr{\"o}der trees has linearexpected complexity and my algorithm that generates Motzkin trees is inO(n) expected complexity, only if we can implement a specific oraclewith a O(1) complexity. For Motzkin trees, I propose a solution whichworks well for realistic values (up to size ten millions) and yields anefficient algorithm.

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives and brought us some beautiful formulas and combinatorial interpretations. The flagship hook-length formula counts the number of Standard Young Tableaux, which also gives the dimension of the irreducible Specht modules of the Symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory. We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, that could formally explain the beauty we see and the difficulties we encounter in finding further formulas and ``combinatorial interpretations''. A 85-year-old such problem asks for a positive combinatorial formula for the Kronecker coefficients of the Symmetric group, another one pertains to the plethysm coefficients of the General Linear group. In the opposite direction, the study of Kronecker and plethysm coefficients leads to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation theoretic multiplicities in further detail, possibly asymptotically., Notes associated with the Current Developments in Mathematics 2023 talk

We study the election control problem with multi-votes, where each voter can present a single vote according different views (or layers, we use "layer" to represent "view"). For example, according to the attributes of candidates, such as: education, hobby or the relationship of candidates, a voter may present different preferences for the same candidate set. Here, we consider a new model of election control that by assigning different rules to the votes from different layers, makes the special candidate p being the winner of the election (a rule can be assigned to different layers). Assuming a set of candidates C among a special candidate "p", a set of voters V, and t layers, each voter gives t votes over all candidates, one for each layer, a set of voting rules R, the task is to find an assignment of rules to each layer that p is acceptable for voters (possible winner of the election). Three models are considered (denoted as sum-model, max-model, and min-model) to measure the satisfaction of each voter. In this paper, we analyze the computational complexity of finding such a rule assignment, including classical complexity and parameterized complexity. It is interesting to find out that 1) it is NP-hard even if there are only two voters in the sum-model, or there are only two rules in sum-model and max-model; 2) it is intractable with the number of layers as parameter for all of three models; 3) even the satisfaction of each vote is set as dichotomous, 1 or 0, it remains hard to find out an acceptable rule assignment. Furthermore, we also get some other intractable and tractable results., 18 pages, 1 figures