Analysis of genomes evolving by inversions leads to a general
combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of
sorting a permutation by a minimum number of reversals.
This combinatorial problem has a long history, and a number of other
motivations. It was studied in a great ... more >>>

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

Local receptive field neurons comprise such well-known and widely
used unit types as radial basis function neurons and neurons with
center-surround receptive field. We study the Vapnik-Chervonenkis
(VC) dimension of feedforward neural networks with one hidden layer
of these units. For several variants of local receptive field
neurons we show ... more >>>