We consider sets ${\it\Gamma}(n,s,k)$ of narrow clauses expressing that no definition of a size $s$ circuit with $n$ inputs is refutable in resolution R in $k$ steps. We show that every CNF with a short refutation in extended R, ER, can be easily reduced to an instance of ${\it\Gamma}(0,s,k)$ (with $s,k$ depending on the size of the ER-refutation) and, in particular, that ${\it\Gamma}(0,s,k)$ when interpreted as a relativized NP search problem is complete among all such problems provably total in bounded arithmetic theory $V_{1}^{1}$ . We use the ideas of implicit proofs from Krajíček [J. Symbolic Logic, 69 (2) (2004), 387–397; J. Symbolic Logic, 70 (2) (2005), 619–630] to define from ${\it\Gamma}(0,s,k)$ a nonrelativized NP search problem $i{\it\Gamma}$ and we show that it is complete among all such problems provably total in bounded arithmetic theory $V_{2}^{1}$ . The reductions are definable in theory $S_{2}^{1}$ . We indicate how similar results can be proved for some other propositional proof systems and bounded arithmetic theories and how the construction can be used to define specific random unsatisfiable formulas, and we formulate two open problems about them.

We show that every finitely generated algebra that is a finitely generated module over a finitely generated commutative subalgebra is an automaton algebra in the sense of Ufnarovskii.

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006), establish a beautiful picture of the computational complexity of approximating the partition function of the hard-core model. Let λc($\mathbb{T}_{\Delta}$) denote the critical activity for the hard-model on the infinite Δ-regular tree. Weitz presented an FPTAS for the partition function when λ < λc($\mathbb{T}_{\Delta}$) for graphs with constant maximum degree Δ. In contrast, Sly showed that for all Δ ⩾ 3, there exists εΔ > 0 such that (unless RP = NP) there is no FPRAS for approximating the partition function on graphs of maximum degree Δ for activities λ satisfying λc($\mathbb{T}_{\Delta}$) < λ < λc($\mathbb{T}_{\Delta}$) + εΔ.

We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Sinclair, Srivastava and Thurley (2014) extended Weitz's approach to the antiferromagnetic Ising model, yielding an FPTAS for the partition function for all graphs of constant maximum degree Δ when the parameters of the model lie in the uniqueness region of the infinite Δ-regular tree. We prove the complementary result for the antiferromagnetic Ising model without external field, namely, that unless RP = NP, for all Δ ⩾ 3, there is no FPRAS for approximating the partition function on graphs of maximum degree Δ when the inverse temperature lies in the non-uniqueness region of the infinite tree $\mathbb{T}_{\Delta}$. Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

Suppose that X1, X2, . . . are independent identically distributed Bernoulli random variables with mean p. A Bernoulli factory for a function f takes as input X1, X2, . . . and outputs a random variable that is Bernoulli with mean f(p). A fast algorithm is a function that only depends on the values of X1, . . ., XT, where T is a stopping time with small mean. When f(p) is a real analytic function the problem reduces to being able to draw from linear functions Cp for a constant C > 1. Also it is necessary that Cp ⩽ 1 − ε for known ε > 0. Previous methods for this problem required extensive modification of the algorithm for every value of C and ε. These methods did not have explicit bounds on $\mathbb{E}[T]$ as a function of C and ε. This paper presents the first Bernoulli factory for f(p) = Cp with bounds on $\mathbb{E}[T]$ as a function of the input parameters. In fact, supp∈[0,(1−ε)/C]$\mathbb{E}[T]$ ≤ 9.5ε−1C. In addition, this method is very simple to implement. Furthermore, a lower bound on the average running time of any Cp Bernoulli factory is shown. For ε ⩽ 1/2, supp∈[0,(1−ε)/C]$\mathbb{E}[T]$≥0.004Cε−1, so the new method is optimal up to a constant in the running time.

The aim of the discrete logarithm problem with auxiliary inputs is to solve for ${\it\alpha}$, given the elements $g,g^{{\it\alpha}},\ldots ,g^{{\it\alpha}^{d}}$ of a cyclic group $G=\langle g\rangle$, of prime order $p$. The best-known algorithm, proposed by Cheon in 2006, solves for ${\it\alpha}$ in the case where $d\mid (p\pm 1)$, with a running time of $O(\sqrt{p/d}+d^{i})$ group exponentiations ($i=1$ or $1/2$ depending on the sign). There have been several attempts to generalize this algorithm to the case of ${\rm\Phi}_{k}(p)$ where $k\geqslant 3$. However, it has been shown by Kim, Cheon and Lee that a better complexity cannot be achieved than that of the usual square root algorithms.

We propose a new algorithm for solving the DLPwAI. We show that this algorithm has a running time of $\widetilde{O}(\sqrt{p/{\it\tau}_{f}}+d)$ group exponentiations, where ${\it\tau}_{f}$ is the number of absolutely irreducible factors of $f(x)-f(y)$. We note that this number is always smaller than $\widetilde{O}(p^{1/2})$.

In addition, we present an analysis of a non-uniform birthday problem.

A k-uniform hypergraph H = (V, E) is called ℓ-orientable if there is an assignment of each edge e ∈ E to one of its vertices v ∈ e such that no vertex is assigned more than ℓ edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the ℓ-orientability of Hn,m,k for all k ⩾ 3 and ℓ ⩾ 2, that is, we determine a critical quantity c*k,ℓ such that with probability 1 − o(1) the graph Hn,cn,k has an ℓ-orientation if c < c*k,ℓ , but fails to do so if c > c*k,ℓ .

Our result has various applications, including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.

A prime sieve is an algorithm that finds the primes up to a bound $n$. We say that a prime sieve is incremental, if it can quickly determine if $n+1$ is prime after having found all primes up to $n$. We say a sieve is compact if it uses roughly $\sqrt{n}$ space or less. In this paper, we present two new results.

–

We describe the rolling sieve, a practical, incremental prime sieve that takes $O(n\log \log n)$ time and $O(\sqrt{n}\log n)$ bits of space.

The second result solves an open problem given by Paul Pritchard in 1994.

We consider ‘unconstrained’ random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in $\mathbb{F}$2 over n variables, each equation containing k ⩾ 3 variables, and also consider a ‘constrained’ model where every variable appears in at least two equations. Dubois and Mandler proved that m/n = 1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analysed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT.

We show that m/n = 1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k ⩾ 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that m − n → −∞ implies almost-sure satisfiability, while m − n → +∞ implies almost-sure unsatisfiability.

We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines of the theory developed by Blum, Shub and Smale for computations over $\mathbb{R}$ (which in turn followed those of the classical, discrete, complexity theory as laid down by Cook, Karp, and Levin, among others). In particular, we focus on complexity classes of decision problems and, paramount among them, on appropriate versions of the classes $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{EXP}$ of polynomial, nondeterministic polynomial, and exponential time, respectively. We prove some basic relationships between these complexity classes, and provide natural NP-complete problems.

This paper revisits the solution of the word problem for ${\it\omega}$-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond’s algorithm, based on normal forms for such terms, uses McCammond’s solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond’s algorithm, based on properties of certain regular languages associated with the normal forms. This method leads to new applications.

We compute coherent presentations of Artin monoids, that is, presentations by generators, relations, and relations between the relations. For that, we use methods of higher-dimensional rewriting that extend Squier’s and Knuth–Bendix’s completions into a homotopical completion–reduction, applied to Artin’s and Garside’s presentations. The main result of the paper states that the so-called Tits–Zamolodchikov 3-cells extend Artin’s presentation into a coherent presentation. As a byproduct, we give a new constructive proof of a theorem of Deligne on the actions of an Artin monoid on a category.

We answer the following question posed by Lechuga: given a simply connected space X with both H* (X; ℚ) and π*(X) ⊗ ℚ being finite dimensional, what is the computational complexity of an algorithm computing the cup length and the rational Lusternik—Schnirelmann category of X?

Basically, by a reduction from the decision problem of whether a given graph is k-colourable for k ≥ 3, we show that even stricter versions of the problems above are NP-hard.

In this work we consider the mean-field traveling salesman problem, where the intercity distances are taken to be independent and identically distributed with some distribution F. We consider the simplest approximation algorithm, namely, the nearest-neighbor algorithm, where the rule is to move to the nearest nonvisited city. We show that the limiting behavior of the total length of the nearest-neighbor tour depends on the scaling properties of the density of F at 0 and derive the limits for all possible cases of general F.

A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a one-dimensional cellular automaton, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to also be a PCA. Last, we focus on the PCA majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.

From power series expansions of functions on curves over finite fields, one can obtain sequences with perfect or almost perfect linear complexity profile. It has been suggested by various authors to use such sequences as key streams for stream ciphers. In this work, we show how long parts of such sequences can be computed efficiently from short ones. Such sequences should therefore be considered to be cryptographically weak. Our attack leads in a natural way to a new measure of the complexity of sequences which we call expansion complexity.

Estimator algorithms in learning automata are useful tools for adaptive, real-time optimization in computer science and engineering applications. In this paper we investigate theoretical convergence properties for a special case of estimator algorithms - the pursuit learning algorithm. We identify and fill a gap in existing proofs of probabilistic convergence for pursuit learning. It is tradition to take the pursuit learning tuning parameter to be fixed in practical applications, but our proof sheds light on the importance of a vanishing sequence of tuning parameters in a theoretical convergence analysis.

Let G be a group generated by k elements, G=〈g1,…,gk〉, with group operations (multiplication, inversion and comparison with identity) performed by a black box. We prove that one can test whether the group G is abelian at a cost of O(k) group operations. On the other hand, we show that a deterministic approach requires Ω(k2) group operations.

Non-degenerate monoids of skew type are considered. This is a class of monoids S defined by n generators and quadratic relations of certain type, which includes the class of monoids yielding set-theoretic solutions of the quantum Yang–Baxter equation, also called binomial monoids (or monoids of I-type with square-free defining relations). It is shown that under any degree-lexicographic order on the associated free monoid FMn. of rank n the set of normal forms of elements of S is a regular language in FMn. As one of the key ingredients of the proof, it is shown that an identity of the form xN yN = yN xN holds in S. The latter is derived via an investigation of the structure of S viewed as a semigroup of matrices over a field. It also follows that the semigroup algebra K[S] is a finite module over a finitely generated commutative subalgebra of the form K[A] for a submonoid A of S.

This paper presents an extension of a result by Guessarian and Niar to the framework of multitransition systems. In the case of a single process, Guessarian and Niar had shown that the set of fair computations of regular SCCS processes coincides with the class of ε-free ω-regular languages. Here, in the case of multitransition systems, we show essentially that the sets of fair computations on multitransition systems are strictly included in the class of ε-free ω-regular N-languages. The inclusions of these fair sets into the class of ε-free ω-regular N-languages are obtained by showing that the strict (respectively weak, strong) fair condition can be simulated by the Muller acceptance condition on multitransition systems. The strictness of the inclusions is obtained by exhibiting two counter-examples showing that the reverse is false, that is, not every ω-regular N-language is the set of fair computations of some multitransition system.

The computation of growth series for the higher Baumslag–Solitar groups is an open problem first posed by de la Harpe and Grigorchuk. We study the growth of the horocyclic subgroup as the key to the overall growth of these Baumslag–Solitar groups BS(p,q), where 1<p<q. In fact, the overall growth series can be represented as a modified convolution product with one of the factors being based on the series for the horocyclic subgroup. We exhibit two distinct algorithms that compute the growth of the horocyclic subgroup and discuss the time and space complexity of these algorithms. We show that when p divides q, the horocyclic subgroup has a geodesic combing whose words form a context-free (in fact, one-counter) language. A theorem of Chomsky–Schützenberger allows us to compute the growth series for this subgroup, which is rational. When p does not divide q, we show that no geodesic combing for the horocyclic subgroup forms a context-free language, although there is a context-sensitive geodesic combing. We exhibit a specific linearly bounded Turing machine that accepts this language (with quadratic time complexity) in the case of BS(2,3) and outline the Turing machine construction in the general case.