Motivated by questions in Social Choice Theory I will consider
the following extremal problem in Combinatorial Geometry. Call a
sequence of vectors of length n with −1, 1 entries feasible if it
contains a subset whose sum is positive in more than n...
The goal of (general-purpose) program obfuscation is to make an
arbitrary computer program "unintelligible" while preserving its
functionality. The problem of program obfuscation is well studied
both in theory and in practice. Though despite its...
In this lecture, I will talk about moment based SDP hierarchies
(which are duals of SOS relaxations for polynomial optimization) in
the context of graph partitioning. The focus will be on a certain
way of rounding such hierarchies, whose quality is...
For a permutation p, let Sn(p) be the number of permutations on
n letters avoiding p. Stanley and Wilf conjectured that, for each
permutation p, Sn(p)1/n tends to a finite limit L(p). Marcus and
Tardos proved the Stanley-Wilf conjecture by a...
A common way for lower bounding the expansion of a graph is by
looking the second smallest eigenvalue of its Laplacian matrix.
Also known as the easy direction of Cheeger's inequality, this
bound becomes too weak when the expansion is o(1). In 2004...
Deep learning, a modern version of neural nets, is increasingly
seen as a promising way to implement AI tasks such as speech
recognition and image recognition. Most current algorithms are
heuristic and have no provable guarantees. This talk will...
The Depth First Search (DFS) algorithm is one of the most
standard graph exploration algorithms, used normally to find the
connected components of an input graph. Though perhaps less popular
than its sister algorithm, Breadth First Search (BFS)...
The Kakeya and restriction conjectures are two of the central
open problems in Euclidean Fourier analysis (with the second
logically implying the first, and progress on the first typically
implying progress on the second). Both of these have...
Finding cliques in random graphs and the closely related
"planted" clique variant, where a clique of size k is planted in a
random G(n,1/2) graph, have been the focus of substantial study in
algorithm design. Despite much effort, the best known...
In this talk I will describe nondeterministic reductions which
yield new direct product theorems (DPTs) for Boolean circuits. In
our theorems one assumes that a function F is "mildly hard" against
*nondeterministic* circuits of some size s(n) , and...
