This is an old revision of the document!

### Sandwiching CNF formulas with sparse polynomials

Contact: Omid Etesami
Room: BC150
Tel:
Email: omid [dot] etesami

A formula of the form 1) is called a Conjunctive Normal Form (CNF) formula. CNF formulas are important in the theory of computation; for example, the problem of whether a CNF formula is satisfiable or not is the canonical NP-complete problem.

A question that arises is whether one can approximate the function computed by a CNF formula with simple functions like sparse polynomials, more precisely, multivariate polynomials with few monomials and small coefficients. Finding such an approximation has applications in computational learning theory.

In this project however, the concern is to find a sparse polynomial that not only approximates the CNF formula but also is always an upper-bound or always a lower-bound to the formula. Furthermore, we don't need just one approximation, but rather a pair of approximations one of which is a lower-bound and the other an upper-bound. Such a pair of approximations is said to “sandwich” the CNF formula.

But why is this problem of sandwiching interesting? At least one reason is that the problem has applications in pseudorandomness. Briefly speaking, pseudorandomness is concerned with creating randomness in a deterministic world devoid of randomness.

There are some theoretical results for this problem of sandwiching CNF formulas, but the problem is not yet fully understood. The goal of this project is to look at this problem from an experimental side. The project can more or less be specified in two general steps:

1. Using linear programming to find the best sparse polynomial sandwiching pair for different CNF formulas;

2. Finding general patterns in the sandwiching pairs obtained in step 1. Recognizing patterns requires creativity. The ultimate goal is to find new patterns for constructing sandwiching pairs better than currently understood methods.

The prerequisite is being comfortable with the basics of linear programming, discrete probability, linear algebra, and ability to implement algorithms.

1) x_1 or x_2 or x_3) and (not x_1 or x_2