 |
Assignment #1:
We saw that dimension-d degree-r
polynomials are alpha-codes; for which alpha? Write down the expression
for the dimension-d low-degree-extension (LDE)
of a string sigma in {0,1}n
- Show that for a boolean function f there exsits a subset I of [n]
of size n/10 so that f is 1/log n far from a Junta over I
- Finite-Field Geometry, in 3-dimensional space: Show that
a. Two planes cannot intersect by only a point; They are either
parallel or intersect by a line.
b. For any given line l, only a |F|-1 fraction of the planes
do not intersect l.
- Show that, for a given assignments A, and let G(A) be the consistency
graph for A:
g(G[A])
£
g(A)
+ |Á|-1
- Show that the algorithm, described in class, for clique'ing the graph:
a. Removes at most 3*(sqrt(beta(G)))* (1/2)|G|^2 of G's edges.
b. The resulting graph is indeed transitive.
- Prove the theorem [RaSa] for general d, and for delta >= |F|^c
(or at least for delta >= d*(|f|^c))
- Prove the "Lemma of Large Clique":
In a transitive graph G, whose edges are a fraction g
of the pairs of vertices, there must be at least one clique
of at least g(G)*|G|
vertices.
- Prove the Large
Clique’s Consistency Lemma over G(A):
A large (>
|Á|-½)
clique
in G(A) agrees almost everywhere
with a single degree-r polynomial
|
|
Assignment
#3:
-
- Given an assignment
to a longcode A:BP[R] ® {0, 1}, show
that for any (constant) d > 0, there
is a constant h(d), which depends
on d
however
does not depend on R, such that:
| {e Î
R | D(Ee,
A) > ½ + d } | £ h(d)
where D(A1,
A2)
is the fraction
of bits A1
and
A2 differ on
|
Consistency Tests (locally testable)