Seminars

Apr
22
2015

MINI-WORKSHOP ON PSEUDORANDOMNESS

The Correlation of Multiplicative Characters with Polynomials over Finite Fields
11:30am|S-101
This talk will focus on the complexity of the cubic-residue (and higher-residue) characters over GF(2^n) , in the context of both arithmetic circuits and polynomials. We show that no subexponential-size, constant-depth arithmetic circuit over GF(2)...
Apr
22
2015

MINI-WORKSHOP ON PSEUDORANDOMNESS

Random Walks in Linear Groups
Peter Varju
10:15am|S-101
I will talk about a joint work with Jean Bourgain that establishes spectral gaps for random walks on SL_n(Z/qZ). Let S be a fixed finite and symmetric subset of SL_n(Z) which generates a Zariski dense subgroup. We show that words of length C log(q)...
Apr
13
2015

Computer Science/Discrete Mathematics Seminar I

A new approach to the sensitivity conjecture
11:15am|S-101

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial...

Apr
07
2015

Computer Science/Discrete Mathematics Seminar II

Interleaved products in special linear groups: mixing and communication complexity
10:30am|S-101

Let $S$ and $T$ be two dense subsets of $G^n$, where $G$ is the special linear group $\mathrm{SL}(2,q)$ for a prime power $q$. If you sample uniformly a tuple $(s_1,\ldots,s_n)$ from $S$ and a tuple $(t_1,\ldots,t_n)$ from $T$ then their interleaved...

Apr
06
2015

Computer Science/Discrete Mathematics Seminar I

Natural algorithms for flow problems
Nisheeth Vishnoi
11:15am|S-101
In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze...
Mar
31
2015

Computer Science/Discrete Mathematics Seminar II

Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
10:30am|S-101

A square matrix $V$ is called rigid if every matrix obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to...

Mar
30
2015

Computer Science/Discrete Mathematics Seminar I

Intelligent learning: similarity control and knowledge transfer
Vladimir Vapnik
11:15am|S-101

During last fifty years a strong machine learning theory has been developed. This theory includes: 1. The necessary and sufficient conditions for consistency of learning processes. 2. The bounds on the rate of convergence which in general cannot be...

Mar
24
2015

Computer Science/Discrete Mathematics Seminar II

Tractability as compressibility
Dimitris Achlioptas
10:30am|S-101
Given a collection of constraints over a collection of variables consider the following generic constraint satisfaction algorithm: start with a random assignment of values to the variables; while violated constraints exist, select a random such...
Mar
23
2015

Computer Science/Discrete Mathematics Seminar I

Random walks that find perfect objects and the Lovász local lemma
Dimitris Achlioptas
11:15am|S-101
At the heart of every local search algorithm is a directed graph on candidate solutions (states) such that every unsatisfactory state has at least one outgoing arc. In stochastic local search the hope is that a random walk will reach a satisfactory...
Mar
17
2015

Computer Science/Discrete Mathematics Seminar II

Average-case lower bounds for formula size
10:30am|S-101
We give an explicit example for a Boolean function $f : \{0,1\}^n \to \{0,1\}$, such that every Boolean formula of size at most $n^{2.999}$, with gates AND, OR and NOT, computes $f$ correctly on at most $1/2 + \epsilon$ fraction of the inputs, where...