The dynamics of large networks is an important and fascinating problem. Key examples are the Internet, social networks, and the human brain. In this paper we consider a model introduced by DeVille and Peskin [6] for a stochastic pulse-coupled neural network. The key feature and novelty in their approach is that they describe the interactions of a neuronal system as a discrete-state stochastic dynamical network. This idealization has two benefits: it captures essential features of neuronal behavior, and it allows the study of spontaneous synchronization, an important phenomenon in neuronal networks that is well-studied but unfortunately far from being well-understood. In synchronous behavior the firing of one neuron leads to the firing of other neurons, which in turn may set off a chain reaction that often involves a substantial proportion of the neurons. In this paper we rigorously analyze their model. In particular, by applying methods and tools that are frequently used in theoretical computer science, we provide a very precise picture of the dynamics and the evolution of the given system. In particular, we obtain insights into the coexistence of synchronous and asynchronous behavior and the conditions that trigger a “spontaneous” transition from one state to another.

We consider liar games in which player Paul must ask one full batch of questions, receive all answers, and then ask a second and final batch of questions. We show that the effect of this restriction is asymptotically negligible. The strategy for Paul is given explicitly.

Randomization is vital in cryptography: secret keys should be randomly generated and most cryptographic primitives (e.g., encryption) must be probabilistic. We initiate the quantitative study concerning feasibility of building secure cryptographic primitives using imperfect random sources. Specifically, we concentrate on symmetric-key encryption and message authentication, where the shared secret key comes from an imperfect random source instead of being assumed truly random. In each case, we compare the class of "cryptographic" sources for the task at hand with the classes of "extractable" and "simulatable" sources, where: (1) "cryptographic" refers to sources for which the corresponding symmetric-key primitive can be built; (2) "extractable" refers to a very narrow class of sources from which one can extract nearly perfect randomness; and (3) "simulatable" refers to a very general class of weak random sources which are known to suffice for BPP simulation. For both encryption and authentication, we show that the corresponding cryptographic sources lie strictly in between extractable and simulatable sources, which implies that "cryptographic usage" of randomness is more demanding than the corresponding "algorithmic usage", but still does not require perfect randomness. Interestingly, cryptographic sources for encryption and authentication are also quite different from each other, which suggests that there might not be an elegant way to describe imperfect sources sufficient for "general cryptographic use". We believe that our initial investigation in this new area will inspire a lot of further research.

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n 2 /e 3 tends to a positive constant as n→∈fty and n l e l n 2 . Similar results hold for graph drawings on any other surface of fixed genus.

Given an n × n matrix A = [aij], a transversal of A is a set of elements, one from each row and one from each column. A transversal is a latin transversal if no two elements are the same. Erdös and Spencer showed that there always exists a latin transversal in any n × n matrix in which no element appears more than s times, for s⩽ (n — 1)/16. Here we show that, in fact, the elements of the matrix can be partitioned into n disjoint latin transversals, provided n is a power of 2 and no element appears more than εn times for some fixed ε>0. The assumption that n is a power of 2 can be weakened, but at the moment we are unable to prove the theorem for all values of n.

One of this author's favorite theorems has long been the Zero-One law discovered independently by Glebskii et al. [12] and Ron Fagin [10]. Let A be any first-order property of graphs and let µ n (A) be the proportion of labelled graphs on n vertices for which A holds. Then This result has inspired much work by logicians, generally in the direction of showing (1) for some powerful languages. Thus it is known [5] that (1) holds when A is a sentence in fixed point logic and it is known [13] that (1) does not always hold when A is a sentence in second-order monadic logic. Here, however, we explore recent work in a totally different direction. Let G(n, p) denote the random graph on n vertices with edge probability p . (In §2 we define the random structures we will deal with.) A property A is an event in the probability space and Pr[ G ( n, p ) ╞ A ] is well defined. When p = 1/2, each labelled graph on n vertices has equal weight so that (1) may be rewritten Fagin's proof actually gives that (2) holds for any constant 0 < p < 1.

Paul tries to find an unknown x from l to n by asking q Yes-No questions. In response Carole may lie up to k times. For k fixed and n, q sufficiently large, necessary and sufficient conditions are given for Paul to win.

A new version of the Lovász Local lemma is used to prove the existence of Latin transversals in matrices where no symbol appears too often.

An $O( n^3 \log n )$ algorithm is presented that, for a given tournament on n vertices, produces a ranking with fit at least $\frac{1}{2} \begin{pmatrix} n \\ 2 \end{pmatrix} + c_1 n^{3/ 2} $, where $c_1 = \frac{1}{8}\pi ^{ - 1 / 2} $.

A series of explicit low-rate binary linear codes that have relatively low covering radius and can be rapidly decoded is exhibited. These codes can be derived from higher-dimensional analogs of the Gale-Berlekamp switching game. Conjectures of independent interest involving Hadamard matrices are given that could yield semiexplicit covering codes of very low density.>

Let G = G(n, p) be the random graph with n vertices and edge probability p and ƒ(n, p, A) be the probability that G has A, where A is a first order property of graphs. The evolution of the random graph is discussed in terms of a spectrum of p = p(n) where ƒ(n, p, A) changes. A partial characterization of possible spectra is given. When p = n-a, a irrational, and A is any first order statement, it is shown that lim ƒ(n, p, A) = 0 or 1.

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log2n+E.log2log2n+O(E.log2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed.