41342139
Techniques for bounding the convergence rate of genetic algorithms
The main purpose of the present paper is the study of computational aspects, and primarily the convergence rate, of Genetic Algorithms (GA’s). Despite the fact that such algorithms are widely used in practice, little is known so far about their theoretical properties, and in particular about their long-term behaviour. This situation is perhaps not too surprising, given the inherent hardness of analyzing nonlinear dynamical systems, and the complexity of the problems to which GA’s are usually applied. In the present paper we concentrate on a number of very simple and natural systems of this sort, and show that at least for these systems the analysis can be property carried out. Various properties and tight quantitative bounds on the long-term behavior of such systems are established. It is our hope that the techniques developed for analyzing these simple systems will prove to be applicable to a wider range of Genetic Algorithms, and contribute to the development of the mathematical foundations of this promising optimization method.
14219969
Superpolynomial Lower Bounds for Monotone Span Programs
monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes.We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields.
10033815
Expanders In Group Algebras
Let G be a finite group and let p be a prime such that (p, |G|) = 1. We study conditions under which the Abelian group $$\Bbb F$$p[G] has a few G-orbits whose union generate it as an expander (equivalently, all the discrete Fourier coefficients (in absolute value) of this generating set are bounded away uniformly from one).We prove a (nearly sharp) bound on the distribution of dimensions of irreducible representations of G which implies the existence of such expanding orbits. We further show a class of groups for which such a bound follows from the expansion properties of G. Together, these lead to a new iterative construction of expanding Cayley graphs of nearly constant degree.
649128
Simple analysis of graph tests for linearity and PCP
We give a simple analysis of the PCP (probabilistically Checkable Proof) with low amortized query complexity of Samorodnitsky and Trevisan (2000). The analysis also applied to the linearity testing over finite fields, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function.
7565108
Space complexity in propositional calculus
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to space bounded Turing machines with a read-only input tape, and such popular propositional proof systems as Resolution, Polynomial Calculus and Frege systems. We study two different space measures. The first, introduced by [5] for Resolution and extended here to other systems, is the structured measure which counts the number of clauses/monomials kept is memory simultaneously. The other is an unstructured °measure related to the number of b i t s describing the memory content. We develop lower bound techniques that enable proving tight linear lower bounds for the first measure, and tight quadratic lower bounds for the second, for large classes of tautologies (including familiar ones like the pigeonhole principle), in both Resolution and (extensions of) Polynomial Calculus. We also prove some structural results concerning the clause space for Resolution and Frege Systems.
45550157
Space Complexity in Propositional Calculus
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape and such popular propositional proof systems as resolution, polynomial calculus, and Frege systems. We propose two different space measures, corresponding to the maximal number of bits, and clauses/monomials that need to be kept in the memory simultaneously. We prove a number of lower and upper bounds in these models, as well as some structural results concerning the clause space for resolution and Frege systems.
6164458
Rubber bands, convex embeddings and graph connectivity
We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and “physical” properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ℝk−1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium.As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allk≧√n, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.
17896683
On the second eigenvalue of hypergraphs
where n = |V |. Let G = (V,E) be a 3-uniform hypergraph; i.e. E is a subset of subsets of V of size 3. We consider the space, L(V ), of real valued functions on V with the usual inner product; let e1, . . . , en be the standard basis for L(V ), where ei takes the value 1 on the i-th vertex of V and 0 elsewhere. It is natural to construct from G a trilinear form, that is a map from τ , mapping triples of vectors in L(V ) to R, namely τ  n ∑
12211028
On data structures and asymmetric communication complexity
In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our ``round elimination'' lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the ``round reduction'' techniques used in many previous lower bound proofs. ] 1998 Academic Press
14452021
On Data Structures and Asymmetric Communication Complexity
In this paper we consider two-party communication complexity, the “asymmetric case”, when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our “round elimination” lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the “round reduction” techniques used in many previous lower bound proofs.
1334521
Rectilinear Graphs and their Embeddings
The embedding problem for a class of graphs called rectilinear graphs is discussed. These graphs have applications in many VLSI Layout Problems. An interesting topological characterization of these graphs lead to efficient algorithms for recognizing and embedding rectilinear graphs which are embeddable on the plane.