Name
Abstract | ||
|---|---|---|
A projection is a subset of {0,1}n given by equations of the form xi = xj, xi = \bar{x}j, xi = 0, and xi = 1, where for $1\leq i \leq n$, xi are Boolean variables and $\bar{x}i are their complements. We study monochromatic projections in 2-colorings of an n-dimensional Boolean cube. We also study the dimension of the largest projection contained in a set specified by its density. We prove almost matching lower and upper bounds on the density of a set required to guarantee the existence of a d-dimensional projection. We also prove almost tight upper and lower bounds on the dimension of monochromatic projections in arbitrary Boolean functions. We then prove almost tight upper and lower bounds on the dimension of monochromatic projections in Boolean functions represented by low degree GF(2) polynomials. It follows from these lower bounds that low-degree GF(2) polynomials can define Boolean functions which are close to being extremal with respect to the property of having no large dimensional monochromatic projections. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1137/S0895480197318313 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
boolean function,largest projection,n-dimensional boolean cube,boolean variable,boolean functions,arbitrary boolean function,d-dimensional projection,large dimensional monochromatic projection,lower bound,form xi,monochromatic projection,circuit complexity,ramsey theory | Boolean function,Ramsey theory,Discrete mathematics,Monochromatic color,Combinatorics,Circuit complexity,Polynomial,Upper and lower bounds,Boolean data type,Mathematics,Cube | Journal |
Volume | Issue | ISSN |
11 | 4 | 0895-4801 |
Citations | PageRank | References |
1 | 0.42 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramamohan Paturi | 1 | 1260 | 92.20 |
| Francis Zane | 2 | 610 | 42.52 |