We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 × 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 × 2 matrix–vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete - even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed - a so-called ray particle - can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete.

We introduce Cyclone codes which are rateless erasure resilient codes. They combine Pair codes with Luby Transform (LT) codes by computing a code symbol from a random set of data symbols using bitwise XOR and cyclic shift operations. The number of data symbols is chosen according to the Robust Soliton distribution. XOR and cyclic shift operations establish a unitary commutative ring if data symbols have a length of p - 1 bits, for some prime number p. We consider the graph given by code symbols combining two data symbols. If n/2 such random pairs are given for n data symbols, then a giant component appears, which can be resolved in linear time. We can extend Cyclone codes to data symbols of arbitrary even length, provided the Goldbach conjecture holds. Applying results for this giant component, it follows that Cyclone codes have the same encoding and decoding time complexity as LT codes, while the overhead is upper-bounded by those of LT codes. Simulations indicate that Cyclone codes significantly decreases the overhead of extra coding symbols.

An algorithmic meta theorem for a logic and a class C of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded tree width. We contribute new algorithmic meta theorems, which state that MSO-definable problems are (a) solvable by uniform constant-depth circuit families (AC0 for decision problems and TC0 for counting problems) when restricted to input structures of bounded tree depth and (b) solvable by uniform logarithmic-depth circuit families (NC1 for decision problems and #NC1 for counting problems) when a tree decomposition of bounded width in term representation is part of the input. Applications of our theorems include a TC0-completeness proof for the unary version of integer linear programming with a fixed number of equations and extensions of a recent result that counting the number of accepting paths of a visible pushdown automaton lies in #NC1. Our main technical contributions are a new tree automata model for unordered, unranked, labeled trees; a method for representing the tree automata's computations algebraically using convolution circuits; and a lemma on computing balanced width-3 tree decompositions of trees in TC0, which encapsulates most of the technical difficulties surrounding earlier results connecting tree automata and NC1.

Abstract We present a cryptographicallyt‐private protocol for electronic auctions whose low resource demands make it viable for practical use. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNGs). Our protocol involves a field of (t+ 1)2parties for the generation of the garbled circuit and permits an arbitrary large number of bidders. The computational requirements are low: Onlyt+ 1 parties of the field have to use the PRNG, the remaining parties execute only primitive computations (XOR, permutations and sharing). The bidders have to stay active for one round of communication, independent of each other. Each bidder has to compute onlyt+ 1 XOR‐operations. We present an implementation and evaluate its performance. The observed running time of our protocol is linear in the size of the auction circuit and the number of bidders and, as expected, grows quadratically in the parametert. Copyright © 2010 John Wiley & Sons, Ltd.

Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when "linear time" is replaced by "logarithmic space." The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the log space world.

We present a feasible cryptographically t-private protocol for electronic auctions. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNG). Our protocol involves a field of (t+1)2parties for the generation of the garbled circuit and permits an arbitrary large number of bidders. The computational requirements are low: Only t+1 parties of the field have to use the PRNG, the remaining parties execute simple primitives (XOR, permuting and sharing). Independently from each other, the bidders have to stay active for one round of communication. Furthermore, each bidder has to compute t+1 XOR-operations, only. We present an implementation and evaluate its performance. The observed running time of our protocol is linear in the size of the auction circuit and the number of bidders and, as expected, grows quadratically in the parameter t.

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient to consider only the communication direction from the party with the shorter input to the other party. These facts do not hold for arbitrary Boolean functions in general. Next, gaps between one-way and two-way communication complexity for symmetric Boolean functions are discussed. Finally, we give some generalizations to the case of multiple parties.

Several authors have shown that the PARITY-function cannot be computed by unbounded fanin circuits of small depth and polynomial size. Even more, constant depth k circuits of size exp(n/sup /spl ominus/(1/k)/) give wrong results for PARITY for almost half of all inputs. We generalize these results in two directions. First, we obtain similar tight lower bounds for the average case complexity of circuits, measuring the computational delay instead of the static circuit depth. Secondly, with respect to average delay of unbounded fanin circuits we completely classify all parallel prefix functions, for which PARITY is just one prominent example. It is shown that only two cases can occur: a parallel prefix functions f either has the same average complexity as PARITY, that is the average delay has to be of order O(log n/ loglog s) for circuits of size s, or f can be computed with constant average delay and almost linear size there is no complexity level in between. This classification is achieved by analyzing the algebraic structure of semigroups that correspond to parallel prefix functions. It extends methods developed for bounded fanin circuits by the first author in his Ph.D. Thesis.