Abstract: A subspace design is a collection {H1, H2, .., HM} of subspaces of F_q^m with the property that no
low-dimensional subspace W of F_q^m intersects too many subspaces of the collection. Subspace designs
were introduced by Guruswami and Xing, who used them to give randomized constructions of optimal rate list-decodable
codes over constant size alphabets. Subspace designs were the only non-explicit part of their construction.
In this talk, I will describe some simple explicit constructions of subspace designs.
The constructions themselves are natural and easily described, and are based on univariate polynomials over finite fields.
The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional
subspace W, we construct a nonzero low-degree polynomial P_W that has several roots for each Hi that non-trivially intersects W.
Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with highly
structured roots or many high multiplicity roots tend to be linearly independent.
Joint work with Venkatesan Guruswami
Tuesday, April 16th
Justin Gilmer, Rutgers
"Composition Limits and Separating Examples for some Boolean Function Complexity Measures"
Time: 2:00 PM
Location: Hill 124
Abstract: Block sensitivity, bs(f), and certificate complexity, C(f), are two fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) <= C(f) = O(bs(f)^2). We will discuss an infinite family of examples for which C(f) grows quadratically in bs(f), giving optimal separations between these measures. In order to analyze the complexity of this family of examples, we characterize how these measures behave under function composition. This is a joint work with Michael
Saks and Srikanth Srinivasan.
Tuesday, April 9th
Hoi Nguyen, Yale
"Some universality results for random matrix of dependent entries"
Time: 2:00 PM
Location: Hill 124
Abstract: We will discuss a variant of the circular law for several random matrix models whose entries are not necessarily independent. These ensembles include random doubly stochastic matrix, random elliptic matrix as well as random block matrix.
Tuesday, April 2nd
Van Vu, Yale
"How many real eigenvalues does a random matrix have ?"
Time: 2:00 PM
Location: Hill 124
Abstract: Let M_n be a matrix whose entries are iid random variables with mean 0 and variance 1. As M_n is not
symmetric, one expects that most of its eigenvalues are complex. In fact, the only case when it is clear that
M_n should have a real eigenvalue is when n is odd. (Personally, I fail to see any other reason.)
However, in 1995, Edelman et. al. proved that if the entries are gaussian, then in expectation there are about cn^{1/2} real eigenvalues. Later, Forrester et. al. showed that the variance (of the number of real eigenvalues) is also of order n^{1/2}.
Both proofs rely heavily on properties of the gaussian distribution and cannot be extended to any other distribution.
In this talk, we are going to show that one can obtain similar estimates
for many other model of random matrices, by attacking a much more general problem about universality of local statistics of eigenvalues M_n. While universality is a basic problem in mathematical physics and probability, our leading idea is combinatorial and quite different from approaches used for symmetric matrices.
If time allows, we will discuss several open questions.
(Joint work with Terence Tao.)
Tuesday, March 26th
Jozsef Beck, Rutgers
"What is geometric entropy, and does it really increase?"
Time: 2:00 PM
Location: Hill 124
Abstract: We all know Shannon's entropy of a discrete probability
distribution. Physicists define entropy in thermodynamics and in
statistical mechanics (there are several competing schools), and want to
prove the Second Law, but they
didn't succeed yet (very roughly speaking, the Second Law claims that the
entropy always increases). What I do is motivated by physics, but I ask
a new, strictly combinatorial/geometric question.
Assume that we have a large finite set of points
in the unit square. Is it possible to
define a ``geometric entropy", which increases for ``typical motion"
of the points? If you want to know the answer, please come to my talk.
Tuesday, March 19th
"NO SEMINAR - SPRING BREAK"
Time: 2:00 PM
Location: Hill 124
Tuesday, March 12th
Manor Mendel, Open University of Israel & IAS
"Expanders with respect to random regular graphs"
Time: 2:00 PM
Location: Hill 124
Abstract: A finite regular graph G=(V,E) has a spectral gap if and only if the
following inequality holds true: For any mapping f:V-->H of the vertices
into Hilbert space, the average over all pairs u,v in V of ||f(u)-f(v)||^2
is at most the average over the edges of the same quantity, times the
reciprocal of the normalized spectral gap --- 1/(1- lambda_2(G)).
Motivated in part by applications to coarse embeddability problems, it is
common practice in metric geometry to consider this inequality with
Hilbert space replaced by other metric spaces. However, it was unknown
whether all sequences of expander graphs are equivalent in this respect.
In this talk we will show that the answer to this question is negative by
constructing a 3-regular expander sequence that satisfies with high
probability the above inequality with respect to the shortest path metric
of a random 3 regular graph. The construction uses several tools,
including the zigzag product, Aleksandrov spaces of non-positive
curvature, nonlinear functional analysis, and random graph theory.
Joint work with Assaf Naor
Tuesday, March 5th
Wes Pegden, NYU
"Apollonian structure in the Abelian sandpile"
Time: 2:00 PM
Location: Hill 124
Abstract: The Abelian sandpile is a chip-firing game on the lattice which can be viewed as a simple deterministic analog to stochastic diffusion processes based on random walks. In contrast to its stochastic counterparts, the sandpile produces striking fractal scaling limits which have long resisted explanation, or even precise description. In this talk, we will discuss a new approach to understanding the fractal behavior of the sandpile, which begins by identifying sandpile limits as solutions of a certain PDE. The heart of our results is a surprising connection between the integer superharmonic functions on the lattice which govern this PDE and Apollonian circle packings of the plane, which allows a characterization of certain fractal solutions produced by the sandpile.
Tuesday, February 26th
Hao Huang, IAS
"Extremal problems in Eulerian digraphs"
Time: 2:00 PM
Location: Hill 124
Abstract: Graphs and digraphs behave quite differently, and many classical results for
graphs are often trivially false when extended to general digraphs.
Therefore it is usually necessary to restrict to a smaller family of
digraphs to obtain meaningful results. One such very natural family is
Eulerian digraphs, in which the in-degree equals out-degree at every
vertex.
In this talk, we discuss several natural parameters for Eulerian digraphs and
study their connections. In particular, we show that for any Eulerian
digraph G with n vertices and m arcs, the minimum feedback arc set
(the smallest set of arcs whose removal makes G acyclic) has size at least
m^2/2n^2 +m/2n, and this bound is tight. Using this result, we show
how to find subgraphs of high minimum degrees, and also long cycles in
Eulerian digraphs. These results were motivated by a conjecture of
Bollobas and Scott.
Joint work with Ma, Shapira, Sudakov and Yuster.
Tuesday, February 19th
Huy Le Nguyen, Princeton
"OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings "
Time: 2:00 PM
Location: Hill 124
Abstract: An "oblivious subspace embedding" (OSE) is a distribution over matrices S such that for any low-dimensional subspace V, with high probability over the choice of S, ||Sx||_2 approximately equals ||x||_2 (up to 1+eps multiplicative error) for all x in V simultaneously. Sarlos in 2006 pioneered the use of OSE's for speeding up algorithms for several numerical linear algebra problems. Problems that benefit from OSE's include: approximate least squares regression, low-rank approximation, approximating leverage scores, and constructing good preconditioners.
We give a class of OSE distributions we call "oblivious sparse norm-approximating projections" (OSNAP) that yield matrices S with few rows that are also extremely sparse, yielding improvements over recent work in this area by Clarkson and Woodruff. In particular, we show S can have O(d^2) rows and 1 non-zero entry per column, or even O(d^{1+gamma}) rows and O_gamma(1) non-zero entries per column for any desired constant gamma>0. When applying the latter bound for example to the approximate least squares regression problem of finding x to minimize ||Ax - b||_2 up to a constant factor, where A is n x d for n
>> d, we obtain an algorithm with running time O(nnz(A) + d^{omega + gamma}). Here nnz(A) is the number of non-zero entries in A, and omega is the exponent of square matrix multiplication.
Our main technical result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: i.e. we show that for any U in R^{n x d} with orthonormal columns and random sparse S with appropriately chosen entries and sufficiently many rows, all singular values of SU lie in the interval [1-eps, 1+eps] with good probability.
Joint work with Jelani Nelson (IAS).
Tuesday, February 12th
Mike Saks, Rutgers
"Population recovery with high erasure probability"
Time: 2:00 PM
Location: Hill 124
Abstract: In the population recovery problem (introduced by Dvir, Rao, Wigderson and Yehudayoff)
one has an unknown probability distribution D on binary strings of length
n and want to determine an estimate D* of the distribution such that for each string
x, |D*(x)-D(x)| is at most some desired bound b. Samples can be obtained from the distribution,
but each sample is obscured as follows: for each sampled string, each bit of the
string is independently erased (changed to "?") with some probability q.
In this talk, I'll discuss my recent work with Ankur Moitra showing that
for any constant erasure probability q<1, the distribution D can be well approximated
using a number of samples (and also computaton) that is polynomial in n and 1/b.
This improves on the previous quasi-polynomial time algorithm
of Wigderson and Yehudayoff and the polynomial time algorithm
of Dvir et al which was shown to work for q<.7 by Batman
et al. The algorithm we analyze is implicit in previous work; our main contribution is to
analyze the algorithm. Mathematically, this amounts to showing that
a certain matrix associated with the problem has a ``robust local inverse''
even though its condition number is exponentially small. We use linear
programming duality to reduce the problem to a question about the behavior
of polynomials on the unit complex disk, which we solve using the Hadamard
3-circle theorem from complex analysis.
The talk will be self-contained; in particular, prior knowledge of robust local inverses,
condition numbers, and the Hadamard 3-circle theorem will not be assumed.
Tuesday, February 5th
Or Meir, IAS
"Combinatorial Construction of Locally Testable Codes"
Time: 2:00 PM
Location: Hill 124
Abstract: An error correcting code is said to be locally testable if there is a test that
can check whether a given string is a codeword of the code, or rather far from
the code, by reading only a constant number of symbols of the string. Locally
Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and
since then several constructions of LTCs were suggested.
While the best known construction of LTCs achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. We present a new and arguably simpler construction of LTCs that uses only elementary linear algebra. Finally, our construction matches the parameters of the best known construction.
Tuesday, January 29th
Arnab Bhattacharyya, DIMACS
"Every locally characterized affine-invariant property is testable"
Time: 2:00 PM
Location: Hill 124
Abstract: Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable.
We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized.
Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties.
Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.
This page was last updated on April 15, 2013 at 12:22 pm and is maintained by webmaster@math.rutgers.edu.
For questions regarding courses and/or special permission, please contact
mclausen@math.rutgers.edu.
