This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:projects:details:omid1 [2011/09/22 09:53] etesami |
en:projects:details:omid1 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| The database entry: | The database entry: | ||
| "type" is one of the following: phd theses, phd semester, master thesis, master semester, bachelor semester | "type" is one of the following: phd theses, phd semester, master thesis, master semester, bachelor semester | ||
| - | "status" is one of the following: available, taken, completed (please upgrade accordingly!!!!!!!!!!) | + | "state" is one of the following: available, taken, completed (please upgrade accordingly!!!!!!!!!!) |
| "by" should be filled as soon as the project is taken/completed | "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). | "completed_dt" is the date when the project was completed (YYYY-MM-DD). | ||
| Line 14: | Line 14: | ||
| contactname: Omid Etesami | contactname: Omid Etesami | ||
| contactmail_mail: omid.etesami | contactmail_mail: omid.etesami | ||
| - | contacttel: | + | contacttel: 36793 |
| contactroom: BC150 | contactroom: BC150 | ||
| - | type : master thesis | + | type : master semester |
| - | status : available | + | state : completed |
| - | created_dt : YYYY-MM-DD | + | created_dt : 2011-09-22 |
| taken_dt : YYYY-MM-DD | taken_dt : YYYY-MM-DD | ||
| completed_dt : YYYY-MM-DD | completed_dt : YYYY-MM-DD | ||
| - | by : the full name of the student | + | by : Sona Hunanyan |
| output_media : en:projects:mahdi_thesis.pdf|Download Mahdi's Thesis | output_media : en:projects:mahdi_thesis.pdf|Download Mahdi's Thesis | ||
| table : projects | table : projects | ||
| Line 30: | Line 30: | ||
| /* Description of the 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 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 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. | + | 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. | 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. | + | 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: | 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: | ||