2007-2008 seminars

Abstract: Studying dynamical systems is key to understanding a wide range of phenomena ranging from planets' movement to climate patterns to market dynamics. Various numerical tools have been developed to address specific questions about dynamical...

We consider several natural problems related to the design of approximation algorithms and the analysis of their error bounds. We define a set of sufficient conditions on a function $f:D --> R^+$ and its domain $D$ , so that we can construct good...

A Kakeya set in F^n , where F is a finite field, is a set containing a line in every direction. The finite field Kakeya conjecture states that the size of such sets is bounded from below by C_n*|F|^n , where C_n depends only on the dimension n . I...

Depth-3 arithmetic circuits compute polynomials that can be represented as sums of products of linear functions. In spite of their simple structure, we are far from understanding such circuits. In this talk we will focus on the reconstruction...

A 3-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every 3 consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We...

Recently, algebraic codes which achieve the optimal trade-off between rate and (list) error-correction radius were constructed by a careful "folding" of the Reed-Solomon code. The "low-degree'' nature of this folding operation was crucial to the...