We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a $\frac{3}{4}$-approximation in expectation. In contrast to previously known $\frac{3}{4}$-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a $\frac{3}{4}$-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within $\frac{3}{4} + \varepsilon$ (for any $\varepsilon > 0$). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio $\frac{3}{4}$. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least $\frac{3}{4} {OPT}_{LP}$, where ${OPT}_{LP}$ is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.

We give a randomized variant of Johnson's algorithm for MAX SAT [12] and show that its expected approximation ratio is ¾. Our solution also works in an online setting where variables are revealed one by one together with the clauses they appear in. Our simple algorithm does not use the power of linear programming and, to the best of our knowledge, is the first such algorithm to reach approximation ratio ¾. We also investigate a variant of Johnson's algorithm proposed in [5] that processes variables in random order. Here we show that the expected approximation ratio is worse than ¾, thus providing a partial answer to a question of [5].

The ambiguity of a nondeterministic finite automaton (NFA) $N$ for input size $n$ is the maximal number of accepting computations of $N$ for an input of size $n$. For all $k,r \in \mathbb{N}$ we construct languages $L_{r,k}$ which can be recognized by NFA's with size $k \cdot$poly$(r)$ and ambiguity $O(n^k)$, but $L_{r,k}$ has only NFA's with exponential size, if ambiguity $o(n^k)$ is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998).

We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring and an optimal cycle cover, provided the greedy algorithm happens to merge the strings in a particular way. Thus, when restricting inputs correspondingly, we verify the well-known greedy conjecture, namely, that the approximation ratio of the greedy algorithm is within a factor of two of the optimum, and actually extend the conjecture considerably. We achieve this bound by systematically combining known conditional inequalities about overlaps and period- and string-lengths with a new familiy of string inequalities. We show that conventional systems of conditional inequalities, including the Monge inequalities, are insufficient to obtain our result.

We present a new technique for differentiating deterministic from nondeterministic communication complexity. As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits. In particular, for any function $t : \mathbb{N} \rightarrow \mathbb{N}$ with $t(n) \leq n/2$ we construct a family $(L_{n,t(n)} : n \in \mathbb{N})$ of languages such that $L_{n,t(n)} \subseteq \{0,1\}^{2n}$, ${\rm nc}(L_{n,t(n)}) = O(t(n) \cdot \log_2 \frac{n}{t(n)})$ and ${\rm nc}(\overline{L_{n,t(n)}}) = O\bigl(\frac{n}{t(n) \cdot \log_2 \frac{n}{t(n)}} + \log_2 t(n)\bigr)$, but ${\rm nc}_{o(t(n))}(L_{n,t(n)}) = \Omega\bigl(\frac{n}{\log_2 \frac{n}{t(n)}}\bigr)$. Here ${\rm nc}_r(L)$ is the nondeterministic communication complexity of L, assuming that at most r advice bits are utilized. Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication. As a special case we obtain a family $L_n \subseteq \{0,1\}^{2n}$ of languages with {\rm nc}_{o(\sqrt{n}/\log_2 n)}(L_n) &=& \Omega\biggl(\frac{n}{\log_2 n}\biggr),\\ {\rm nc}(L_n) + {\rm nc}(\overline{L_n}) &=& O(\sqrt{n}), and hence nondeterministic communication with slightly restricted access to advice bits is almost quadratically weaker than nondeterminism that always gives correct answers (from the set {yes, no, ?}). As a consequence we obtain an almost optimal separation between Monte-Carlo communication and "correct" nondeterminism and answer a question of Beame and Lawry.

We consider the familiarity problem: for given pat-tems21,...2, E {O,l}" and input y E (0, l}n one has to decide whether y is sufficiently close to one of the patterns with respect to Hamming distance.Errors are allowed and inputs of intermediate distance are excluded, when evaluating arbitrary memory models for the familiarity problem.We design neural circuits for various distributions and show that the memory complexity of our circuits (i.e., the logarithm of the total number of required circuits) is close to optimal, even when compared to arbitrary memory models.Moreover we obtain near-optimal results simultaneously for the resources memory complexity, depth and number of edges.Additionally the number of vertices can be minimized in a somewhat restricted setting.Circuits for the familiarity problem are considerably smaller in terms of memory complexity, number of edges or number of gates when compared to circuits for the conventional Hamming distance problem.*supported by DFG project Schn .503/l-2Permission to make digital or hard copies of all or p"rt of this work for personal or classroom use is

We present a new technique to differentiate deterministic from nondeterministic communication complexity.As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits (i.e., nondeterministic guesses).In particular, for any function t : N + N (with t(k) < k/2) we construct a family (L~,t(k) : m c N) of languages such that (a) L~,,f~J'~{O, I} 'k, (b) ncc,(~)(L,,,(k)) = O(t(k)), (c) nc%, k(bc,t(k)) = 0("~k ), (d) but IIC%(t(k)/ bg2 k)(~k,t(k)) = '( Iog2(,&t(k)) )" (ncc, (L) is the nondeterministic communication complexity of L, assuming that at most r advice bits are used for any input.) Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication, even if the original number of advice bits is super-logarithmic.

We show that neural networks with three-times continuously differentiable activation functions are capable of computing a certain family of n-bit boolean functions with two gates, whereas networks composed of binary threshold functions require at least omega(log n) gates. Thus, for a large class of activation functions, analog neural networks can be more powerful than discrete neural networks, even when computing Boolean functions.

It is shown that, for inputs of length n, the probabilistic (bounded error) communication complexity of set intersection is $\Theta ( n )$. Since set intersection can be recognized nondeterministically by exchanging $O( \log n )$ bits, the result implies an exponential gap between nondeterminism and probabilism. This gap is the largest possible. The first general technique to analyze the probabilistic communication complexity of sparse languages is also described.

It is shown that in a standard discrete neural network model with small fan-in, tolerance to random malicious faults can be achieved with a log-linear increase in the number of neurons and a constant factor increase in parallel time, provided fan-in can increase arbitrarily. A similar result is obtained for a nonstandard but closely related model with no restriction on fan-in.

The power of constant depth circuits with sigmoid (i.e., smooth) threshold gates for computing Boolean functions is examined. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size Boolean threshold circuits (i.e., circuits with Boolean threshold gates). On the other hand it turns out that, for any constant depth d, polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same Boolean functions as the corresponding circuits with Boolean threshold gates.>

The communication complexity of a function f measures the communication capacity any system computing f must provide.In Lqe design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x t/me 2 .lowerbound.In this paper, we investigate the communication complexity of singdarity testing, where the problem is to determine whether a given square matrix M is singular.We show that, for n x n matrices of k-bit integers, the communication complexity of this problem is O(knZ).In case the entries of M are elements of a finite field of size p , we also prove the communication complexity of this problem to be O(n21ogp ).Oar results are new and imply fight bounds for a wide variety of other problems in Numerical Linear Algebra.Among those problems are determ/n/ng the rank and computing the determinant, as well as the computation of several matr/x decompositions.Another important corollary concerns the solvability of linear systems.In this problem it has to be decided whether a linear system Ax=b has a solution.When A is an

We construct a family (Gp | p) of directed acyclic graphs such that any black pebble strategy for Gp requires p2 pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.

We prove the first superlinear lower bound for a concrete decision problem in P on a Turing machine with one work tape and a two-way input tape (also called: off-line 1-tape Turing machine). In particular we show for off-line Turing machines that 2 tapes are better than 1 and that 3 pushdown stores are better than 2 (both in the deterministic and in the nondeterministic case).

We prove the following four results on communication complexity:

For each ε(0 ≤ ε ≪ 1) a family Gn =(V(Gn), E(Gn)) of a cyclic digraphs can be constructively defined having the following properties: (a) #V(Gn) ≤ n · 2n+2 (b) degree (Gn) ≤ constant (c) it is necessary to remove Ω(n · 2n) edges in order to reduce the depth of Gn to (2n)ε. It is then shown: For suitable constants c1, C2 ≫ 0, there are (fn, n)- grates (see Definition 1) of size linear in n, where fn(x):= c1 · n2 x ≤ c2 ≤'; n/0 otherwise