/* This is the template for project details pages */

/* 
  The database entry:
  "type" is one of the following: phd theses, phd semester, master thesis, master semester, bachelor semester
  "state" is one of the following: available, taken, completed (please upgrade accordingly!!!!!!!!!!) 
  "by" should be filled as soon as the project is taken/completed
  "completed_dt" is the date when the project was completed (YYYY-MM-DD). 
  "output_media" is the link to the pdf of the project (wiki syntax)
  "table" must be "projects" => don't touch it!
*/
---- dataentry project ----
title : Sandwiching CNF formulas with sparse polynomials
contactname: Omid Etesami
contactmail_mail: omid.etesami
contacttel: 36793
contactroom: BC150
type :  master semester
state : completed
created_dt : 2011-09-22
taken_dt : YYYY-MM-DD
completed_dt : YYYY-MM-DD
by : Sona Hunanyan
output_media : en:projects:mahdi_thesis.pdf|Download Mahdi's Thesis
table : projects
======
template:datatemplates:project
----

/* Description of the project */

A formula of the form [(x_1 or x_2 or x_3) and (not x_1 or x_2)] 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 CNF formula defines a function that takes as input an assignment of values to the variables appearing in the formula and evaluates to 1 if the assignment satisfies the formula and 0 otherwise.

A question that arises is whether one can approximate the function defined by a given 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 that we know today 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.