2008-2009 Seminars

A celebrated theorem of Razborov/Smolensky says that constant depth circuits comprising AND/OR/MOD_{p^k} gates of unbounded fan-in, require exponential size to compute the MAJORITY function if p is a fixed prime and k is a fixed integer. Extending...

We study the model of approximation and calculation of constant degree multivariate polynomials over finite fields. We prove that if a constant degree polynomial can be approximated by a function of a constant number of lower degree polynomials, it...

A celebrated theorem of Razborov/Smolensky says that constant depth circuits comprising AND/OR/MOD_{p^k} gates of unbounded fan-in, require exponential size to compute the MAJORITY function if p is a fixed prime and k is a fixed integer. Extending...

Color Coding is an algorithmic technique for deciding efficiently if a given input graph contains a path of a given length (or another small subgraph of a certain type). It illustrates well the phenomenon that probabilistic reasoning can be helpful...

We present the first local list-decoding algorithm for the r-th order Reed-Muller code RM(r,m) over F_2 for r>1 . Given an oracle for a received word R: F_2^m to F_2 , our randomized local list-decoding algorithm produces a list containing all...

One natural strategy for proving a time lower bound for a problem is proof-by-contradiction: assume that there is a great algorithm for the problem, and apply this algorithm as a subroutine to solve other problems until the algorithms get so great...

I will discuss this problem: given rational functions f and g over a field K , determine whether there are nonconstant rational functions u and v over K such that u(f(x)) = v(g(x)) . An equivalent problem is to compute the intersection of two fields...

Nisan and Wigderson defined the model of multilinear circuits as a natural model for computing multilinear polynomials (such as matrix product and the Permanent). We will go over several results regarding such circuits -- a few structural results...

Nisan and Wigderson defined the model of multilinear circuits as a natural model for computing multilinear polynomials (such as matrix product and the Permanent). We will go over several results regarding such circuits -- a few structural results...