Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields

In this paper, we give the first construction of a pseudorandom generator, with seed length O(log n), for CC⁰[p], the class of constant-depth circuits with unbounded fan-in MOD _p gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ${\epsilon > 0}$ . In fact, we obtain our generator by fooling distributions generated by low-degree polynomials, over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed (Luby et al. 1993) or could only fool the distribution generated by linear functions over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube (Lovett et al. 2009; Meka & Zuckerman 2009). En route of constructing our PRG, we prove two structural results for low-degree polynomials over finite fields that can be of independent interest.

1. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . Then, for every ${\epsilon > 0}$ , there exists a subset ${S \subset [n]}$ , whose size depends only on d and ${\epsilon}$ , such that ${\sum_{\alpha \in \mathbb{F}_p^n: \alpha \ne 0, \alpha_S=0}|\hat{f}(\alpha)|^2 \leq \epsilon}$ . Namely, there is a constant size subset S such that the total weight of the nonzero Fourier coefficients that do not involve any variable from S is small.
2. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . If the distribution of f when applied to uniform zero–one bits is ${\epsilon}$ -far (in statistical distance) from its distribution when applied to biased bits, then for every ${\delta > 0}$ , f can be approximated over zero–one bits, up to error δ, by a function of a small number (depending only on ${\epsilon,\delta}$ and d) of lower degree polynomials.

     

On the power of unambiguity in log-space

We report progress on the NL versus UL problem.

We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including ${{{ReachFewL} \subseteq {UL}}}$ and ${{{LFew} \subseteq {UL}^{FewL}}}$

We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes.

We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that ${{{ULH} \subseteq {L}^{{promiseUL}}}}$ thus collapsing the UL hierarchy.

We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages, which is log-space equivalent to the reachability problem in planar graphs and hence is in UL.

     

Association Fields via Cuspless Sub-Riemannian Geodesics in SE(2)

To model association fields that underly perceptional organization (gestalt) in psychophysics we consider the problem P _curve of minimizing $\int _{0}^{\ell} \sqrt{\xi^{2} +\kappa^{2}(s)} {\rm d}s $ for a planar curve having fixed initial and final positions and directions. Here κ(s) is the curvature of the curve with free total length ?. This problem comes from a model of geometry of vision due to Petitot (in J. Physiol. Paris 97:265–309, 2003; Math. Inf. Sci. Humaines 145:5–101, 1999), and Citti & Sarti (in J. Math. Imaging Vis. 24(3):307–326, 2006). In previous work we proved that the range $\mathcal{R} \subset\mathrm{SE}(2)$ of the exponential map of the underlying geometric problem formulated on SE(2) consists of precisely those end-conditions (x _fin,y _fin,θ _fin) that can be connected by a globally minimizing geodesic starting at the origin (x _in,y _in,θ _in)=(0,0,0). From the applied imaging point of view it is relevant to analyze the sub-Riemannian geodesics and $\mathcal{R}$ in detail. In this article we

• show that $\mathcal{R}$ is contained in half space x≥0 and (0,y _fin)≠(0,0) is reached with angle π,
• show that the boundary $\partial\mathcal{R}$ consists of endpoints of minimizers either starting or ending in a cusp,
• analyze and plot the cones of reachable angles θ _fin per spatial endpoint (x _fin,y _fin),
• relate the endings of association fields to $\partial\mathcal {R}$ and compute the length towards a cusp,
• analyze the exponential map both with the common arc-length parametrization t in the sub-Riemannian manifold $(\mathrm{SE}(2),\mathrm{Ker}(-\sin\theta{\rm d}x +\cos\theta {\rm d}y), \mathcal{G}_{\xi}:=\xi^{2}(\cos\theta{\rm d}x+ \sin\theta {\rm d}y) \otimes(\cos\theta{\rm d}x+ \sin\theta{\rm d}y) + {\rm d}\theta \otimes{\rm d}\theta)$ and with spatial arc-length parametrization s in the plane $\mathbb{R}^{2}$ . Surprisingly, s-parametrization simplifies the exponential map, the curvature formulas, the cusp-surface, and the boundary value problem,
• present a novel efficient algorithm solving the boundary value problem,
• show that sub-Riemannian geodesics solve Petitot’s circle bundle model (cf. Petitot in J. Physiol. Paris 97:265–309, [2003]),
• show a clear similarity with association field lines and sub-Riemannian geodesics.

     

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

• Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution.
• Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
• If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.

     

Amplifying circuit lower bounds against polynomial time, with applications

We give a self-reduction for the Circuit Evaluation problem (CircEval) and prove the following consequences.

1. Amplifying size–depth lower bounds. If CircEval has Boolean circuits of n ^k size and n ^1?δ depth for some k and δ, then for every ${\epsilon > 0}$ , there is a δ′ > 0 such that CircEval has circuits of ${n^{1 + \epsilon}}$ size and ${n^{1- \delta^{\prime}}}$ depth. Moreover, the resulting circuits require only ${\tilde{O}(n^{\epsilon})}$ bits of non-uniformity to construct. As a consequence, strong enough depth lower bounds for Circuit Evaluation imply a full separation of P and NC (even with a weak size lower bound).
2. Lower bounds for quantified Boolean formulas. Let c, d > 1 and e < 1 satisfy c < (1 ? e + d )/d. Either the problem of recognizing valid quantified Boolean formulas (QBF) is not solvable in TIME[n ^c ], or the Circuit Evaluation problem cannot be solved with circuits of n ^d size and n ^e depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF. We also prove that QBF does not have n ^c -time uniform NC circuits, for all c < 2.

     

Derandomized Parallel Repetition Theorems for Free Games

Raz’s parallel repetition theorem (SIAM J Comput 27(3):763–803, 1998) together with improvements of Holenstein (STOC, pp 411–419, 2007) shows that for any two-prover one-round game with value at most ${1- \epsilon}$ 1 - ? (for ${\epsilon \leq 1/2}$ ? ≤ 1 / 2 ), the value of the game repeated n times in parallel on independent inputs is at most ${(1- \epsilon)^{\Omega(\frac{\epsilon^2 n}{\ell})}}$ ( 1 - ? ) Ω ( ? 2 n ? ) , where ? is the answer length of the game. For free games (which are games in which the inputs to the two players are uniform and independent), the constant 2 can be replaced with 1 by a result of Barak et al. (APPROX-RANDOM, pp 352–365, 2009). Consequently, ${n=O(\frac{t \ell}{\epsilon})}$ n = O ( t ? ? ) repetitions suffice to reduce the value of a free game from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t , and denoting the input length of the game by m, it follows that ${nm=O(\frac{t \ell m}{\epsilon})}$ n m = O ( t ? m ? ) random bits can be used to prepare n independent inputs for the parallel repetition game. In this paper, we prove a derandomized version of the parallel repetition theorem for free games and show that O(t(m + ?)) random bits can be used to generate correlated inputs, such that the value of the parallel repetition game on these inputs has the same behavior. That is, it is possible to reduce the value from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t while only multiplying the randomness complexity by O(t) when m = O(?). Our technique uses strong extractors to “derandomize” a lemma of Raz and can be also used to derandomize a parallel repetition theorem of Parnafes et al. (STOC, pp 363–372, 1997) for communication games in the special case that the game is free.     

Join-Reachability Problems in Directed Graphs

For a given collection \(\mathcal{G}\) of directed graphs we define the join-reachability graph of \(\mathcal{G}\) , denoted by \(\mathcal{J}(\mathcal{G})\) , as the directed graph that, for any pair of vertices u and v, contains a path from u to v if and only if such a path exists in all graphs of  \(\mathcal{G}\) . Our goal is to compute an efficient representation of  \(\mathcal{J}(\mathcal{G})\) . In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for  \(\mathcal{G}\) . In the implicit version we wish to build an efficient data structure, in terms of space and query time, such that we can report fast the set of vertices that reach a query vertex in all graphs of  \(\mathcal{G}\) . This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problems. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.     

Linear-Space Data Structures for Range Mode Query in Arrays

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 517–526, 2003), requires \(\varTheta (\sqrt{n}\log\log n)\) query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in \(O(\sqrt{n/\log n})\) worst-case time. In the external memory model, we give a linear-space data structure that requires \(O(\sqrt{n/B})\) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below \(\sqrt{n}\) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two \(\sqrt{n} \times \sqrt{n}\) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n ^3/4) time), for orthogonal range mode in d dimensions (queries in near O(n ^1?1/2d ) time) and for half-space range mode in d dimensions (queries in \(O(n^{1-1/d^{2}})\) time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures.     

k-pairwise disjoint paths routing in perfect hierarchical hypercubes

Hierarchical hypercubes (HHC), also known as cube-connected cubes, have been introduced in the literature as an interconnection network for massively parallel systems. Effectively, they can connect a large number of nodes while retaining a small diameter and a low degree compared to a hypercube of the same size. Especially (2 ^m +m)-dimensional hierarchical hypercubes ( $\mathit {HHC}_{2^{m}+m}$ ), called perfect HHCs, are popular as they are symmetrical, which is a critical property when designing routing algorithms. In this paper, we describe an algorithm finding, in an $\mathit{HHC}_{2^{m}+m}$ , mutually node-disjoint paths connecting k=?(m+1)/2? pairs of distinct nodes. This problem is known as the k-pairwise disjoint-path routing problem and is one of the important routing problems when dealing with interconnection networks. In an $\mathit{HHC}_{2^{m}+m}$ , our algorithm finds paths of lengths at most 2 ^m+1+m(2 ^m+1+1)+4 in O(2^5m ) time, where 2 ^m+1 is the diameter of an $\mathit{HHC}_{2^{m}+m}$ . Also, we have shown through an experiment that, in practice, the lengths of the generated paths are significantly lower than the worst-case theoretical estimations.     

Generalising Unit-Refutation Completeness and SLUR via Nested Input Resolution

The class ${\mathcal{SLUR}}$ (Single Lookahead Unit Resolution) was introduced in Schlipf et al. (Inf Process Lett 54:133–137, 1995) as an umbrella class for efficient (poly-time) SAT solving, with linear-time SAT decision, while the recognition problem was not considered. ?epek et al. (2012) and Balyo et al. (2012) extended this class in various ways to hierarchies covering all of CNF (all clause-sets). We introduce a hierarchy ${\mathcal{SLUR}}_k$ which we argue is the natural “limit” of such approaches. The second source for our investigations is the class ${\mathcal{UC}}$ of unit-refutation complete clause-sets, introduced in del Val (1994) as a target class for knowledge compilation. Via the theory of “hardness” of clause-sets as developed in Kullmann (1999), Kullmann (Ann Math Artif Intell 40(3–4):303–352, 2004) and Ansótegui et al. (2008) we obtain a natural generalisation ${\mathcal{UC}}_k$ , containing those clause-sets which are “unit-refutation complete of level k”, which is the same as having hardness at most k. Utilising the strong connections to (tree-)resolution complexity and (nested) input resolution, we develop basic methods for the determination of hardness (the level k in ${\mathcal{UC}}_k$ ). A fundamental insight now is that ${\mathcal{SLUR}}_k = {\mathcal{UC}}_k$ holds for all k. We can thus exploit both streams of intuitions and methods for the investigations of these hierarchies. As an application we can easily show that the hierarchies from ?epek et al. (2012) and Balyo et al. (2012) are strongly subsumed by ${\mathcal{SLUR}}_k$ . Finally we consider the problem of “irredundant” clause-sets in ${\mathcal{UC}}_k$ . For 2-CNF we show that strong minimisations are possible in polynomial time, while already for (very special) Horn clause-sets minimisation is NP-complete. We conclude with an extensive discussion of open problems and future directions. We envisage the concepts investigated here to be the starting point for a theory of good SAT translations, which brings together the good SAT-solving aspects from ${\mathcal{SLUR}}$ together with the knowledge-representation aspects from ${\mathcal{UC}}$ , and expands this combination via notions of “hardness”.     

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E→?⁺, a set T ₁,T ₂,…,T _k of subtrees of G is called a tree cover of G if $V=\bigcup_{i=1}^{k} V(T_{i})$ . In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. Algorithms 59:1–18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309–315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of $\frac{3}{2}$ (Xu and Wen in Oper. Res. Lett. 38:169–173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1–18, 2006).     

Solving visibility and separability problems on a mesh-of-processors

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms:

- AnO( \(\sqrt N\) time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes.

-O( \(\sqrt N\) ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond.

- AnO( \(\sqrt N\) ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( \(\sqrt {MN}\) ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction.

All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.     

Query-Efficient Locally Decodable Codes of Subexponential Length

A k-query locally decodable code (LDC) C : Σ ⁿ → Γ ^N encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (in J ACM 55:1–16, 2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(log n/log log n))), under the assumption that there are infinitely many Mersenne primes. Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) constructed a 3-query LDC of length ${N_{2}={\rm exp}({\rm exp} (O(\sqrt{\log n\log\log n})))}$ with no assumption, and a 2 ^r -query LDC of length ${N_{r}={\rm exp}({\rm exp}(O(\sqrt[r]{\log n(\log \log n)^{r-1}})))}$ , for every integer r ≥ 2. Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010) gave a composition method in Efremenko’s framework and constructed a 3 · 2 ^r-2-query LDC of length N _r , for every integer r ≥ 4, which improved the query complexity of Efremenko’s LDC of the same length by a factor of 3/4. The main ingredient of Efremenko’s construction is the Grolmusz construction for super-polynomial size set-systems with restricted intersections, over ${\mathbb{Z}_m}$ , where m possesses a certain “good” algebraic property (related to the “algebraic niceness” property of Yekhanin in J ACM 55:1–16, 2008). Efremenko constructed a 3-query LDC based on m = 511 and left as an open problem to find other numbers that offer the same property for LDC constructions. In this paper, we develop the algebraic theory behind the constructions of Yekhanin (in J ACM 55:1–16, 2008) and Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009), in an attempt to understand the “algebraic niceness” phenomenon in ${\mathbb{Z}_m}$ . We show that every integer m =  pq = 2 ^t ?1, where p, q, and t are prime, possesses the same good algebraic property as m = 511 that allows savings in query complexity. We identify 50 numbers of this form by computer search, which together with 511, are then applied to gain improvements on query complexity via Itoh and Suzuki’s composition method. More precisely, we construct a ${3^{\lceil r/2\rceil}}$ -query LDC for every positive integer r < 104 and a ${\left\lfloor (3/4)^{51} \cdot 2^{r}\right\rfloor}$ -query LDC for every integer r ≥ 104, both of length N _r , improving the 2 ^r queries used by Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) and 3 · 2 ^r-2 queries used by Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010). We also obtain new efficient private information retrieval (PIR) schemes from the new query-efficient LDCs.     

The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G—a connected dominating set of G—such that (i) S is a dominating set of G, and (ii) the subgraph G[S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, 1999) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set

• does not have a kernel of any size on graphs of girth three or four (since the problem is W[2]-hard);
• admits a kernel of size 2 ^k k ^3k on graphs of girth at least five;
• has no polynomial kernel (unless the Polynomial Hierarchy collapses to the third level) on graphs of girth at most six, and,
• has a cubic ( $\mathcal {O}(k^{3})$ ) vertex kernel on graphs of girth at least seven.

While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.     

An approach to the DIN Kernel Lisp definition

A DIN Kernel LISP Draft (DKLisp) has been developed by DIN as Reaction to Action D1 (N79), short term goal, of ISO WG16. It defines a subset language, as compatible as possible with the ANSICommon-Lisp draft, but also with theEuLisp draft. It combines the most important LISP main stream features in a single, compact, but nevertheless complete language definition, which thereby could be well suited as basis for a short term InternationalLisp Standard. Besides the functional and knowledge processing features, the expressive power of the language is well comparable with contemporary procedural languages, as e.g. C++ (of course without libraries). Important features ofDKLisp are:

to be a “Lisp-1,” but allowing an easy “Lisp-2” transformation;

to be a simple, powerful and standardized educationalLisp;

to omit all features, which are unclean or in heavy discussion;

DKLisp programs run nearly unchanged inCommon-Lisp;

DKLisp contains a simple object and package system;

DKLisp contains those data classes and control structures also common to most modernLisp and non-Lisp languages;

DKLisp offers a simple stream I/O;

DKLisp contains a clean unified hierarchical class/type system;

DKLisp contains the typical “Lisp-features” in an orthogonal way;

DKLisp allows and encourages really small but powerful implementations;

DKLisp comes in levels, so allowing ANSICommon-Lisp to be an extension ofDKLisp level-1.

The present is the second version of the proposal, namely version 1.2, with slight differences with respect to the one sent to ISO. Sources of such changes were the remarks generously sent by many readers of the previous attempt.     

The addition of bounded quantification and partial functions to a computational logic and its theorem prover

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as ‘mapping functions’. The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as ‘capturing’, ‘bottom’, or ‘continuity’. Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are:

? classic quantifier manipulation theorems, such as $$\sum\limits_{{\text{l}} = 0}^{\text{n}} {{\text{g}}({\text{l}}) + {\text{h(l) = }}} \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{g}}({\text{l}})} + \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{h(l)}};} $$

? elementary theorems involving quantifiers, such as the Binomial Theorem: $$(a + b)^{\text{n}} = \sum\limits_{{\text{l = }}0}^{\text{n}} {\left( {_{\text{i}}^{\text{n}} } \right)} \user2{ }{\text{a}}^{\text{l}} {\text{b}}^{{\text{n - l}}} ;$$

? elementary theorems about ‘mapping functions’ such as: $$(FOLDR\user2{ }'PLUS\user2{ O L) = }\sum\limits_{{\text{i}} \in {\text{L}}}^{} {{\text{i}};} $$

? termination properties of many partial recursive functions such as the fact that an application of the partial function described by $$\begin{gathered} (LEN X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F ({\rm E}QUAL X NIL) \hfill \\ {\rm O} \hfill \\ (ADD1 (LEN (CDR X)))) \hfill \\ \end{gathered} $$ terminates if and only if the argument ends in NIL;

? theorems about functions satisfying unusual recurrence equations such as the 91-function and the following list reverse function: $$\begin{gathered} (RV X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F (AND (LISTP X) (LISTP (CDR X))) \hfill \\ (CONS (CAR (RV (CDR X))) \hfill \\ (RV (CONS (CAR X) \hfill \\ (RV (CDR (RV (CDR X))))))) \hfill \\ X). \hfill \\ \end{gathered} $$

     

Pseudorandom generators for combinatorial checkerboards

We define a combinatorial checkerboard to be a function f : {1, . . . , m} ^d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f _i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ .     

Two-Way Automata Versus Logarithmic Space

We strengthen a previously known connection between the size complexity of two-way finite automata ( ) and the space complexity of Turing machines (tms). Specifically, we prove that

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL?L/poly, and

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤2 ^s if and only if NLL?LL/polylog.

Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice.     

Yang-Baxter {\breve R} matrix, entanglement and Yangian

We present a method to construct ??X?? form unitary Yang-Baxter ${\breve R}$ matrices, which act on the tensor product space ${V_{i}^{j_{1}}\otimes V_{i+1}^{j_{2}}}$ . We can obtain a set of entangled states for (2j ₁?+?1)?× (2j ₂?+?1)-dimensional system with these Yang-Baxter ${\breve R}$ matrices. By means of Yang-Baxter approach, a 8?× 8 Yang-Baxter Hamiltonian is constructed. Yangian symmetry and Yangian generators as shift operators for this Yang-Baxter system are investigated in detail.     

Stabilizing maximum matching in bipartite networks

A matching ${E_\mathcal{M}}$ of graph G =  (V, E) is a subset of the edges E, such that no vertex in V is incident to more than one edge in ${E_\mathcal{M}}$ . The matching ${E_\mathcal{M}}$ is maximum if there is no matching in G with size strictly larger than the size of ${E_\mathcal{M}}$ . In this paper, we present a distributed stabilizing algorithm for finding maximum matching in bipartite graphs based on the stabilizing PIF algorithm of Cournier et al. (Proceedings of 21st IEEE international conference on distributed computing systems, 91–98, 2001). Since our algorithm is stabilizing, it does not require initialization and withstands transient faults. The complexity of the proposed algorithm is O(d × n) rounds, where d is the diameter of the communication network and n is the number of nodes in the network. The space complexity is O(log Δ +  log d), where Δ is the largest degree of all the nodes in the communication network. In addition, an optimal version of the proposed algorithm finding maximum matching in linear time is also presented.