Seminars Sorted by Series

I will discuss this problem: given rational functions f and g over a field K , determine whether there are nonconstant rational functions u and v over K such that u(f(x)) = v(g(x)) . An equivalent problem is to compute the intersection of two fields...

We present the first local list-decoding algorithm for the r-th order Reed-Muller code RM(r,m) over F_2 for r>1 . Given an oracle for a received word R: F_2^m to F_2 , our randomized local list-decoding algorithm produces a list containing all...

We study the model of approximation and calculation of constant degree multivariate polynomials over finite fields. We prove that if a constant degree polynomial can be approximated by a function of a constant number of lower degree polynomials, it...

This talk describes new explicit constructions of dispersers for affine sources of dimension below the notorious n/2 threshold. The main novelty in our construction lies in the method of proof which relies (solely) on elementary properties of...

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Denoting by val(G) the value of a two-prover unique game G, and by sdp(G) the value of a natural semidefinite program to...

Razborov and Rudich have shown that so-called natural proofs are not useful for separating P from NP unless hard pseudorandom number generators do not exist. This famous result is widely regarded as a serious barrier to proving strong lower bounds...

We give a (1+eps)-speed Theta(1/eps^2)-competitive nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of total response time.

For a graph G , let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. We study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years...

Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithm/protocol is given...

Recently, Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi introduced a natural metric on the space of dense graphs, and identified the completion of the metric space that arises. Independently and simultaneously, Janson, Riordan and I defined a...

The ``direct product code'' of a function $f$ gives its values on all $k$-tuples $(f(x_1),\dots,f(x_k))$. This basic construct underlies “hardness amplification” in cryptography, circuit complexity and PCPs. A recent breakthrough by Dinur and...

We study combinatorial group testing schemes for learning d-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise...

Since the work of Karp and Lipton in the 1980s, complexity theorists know and love the /poly operator, which adds a polynomial-sized advice string to any complexity class. But it's interesting to consider much more general kinds of "advice objects"...

This series of three talks will give a nontechnical, high level overview of geometric complexity theory (GCT), which is an approach to the P vs. NP problem via algebraic geometry, representation theory, and the theory of a new class of quantum...

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using...

We bound the time it takes for a group of birds to reach steady state in a standard flocking model. We prove that (i) within single exponential time fragmentation ceases and each bird settles on a fixed flying direction; (ii) the flocking network...

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For the algorithm to be local, its complexity must be...

We prove that NP is different from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k=(1 - e)log(n) players, where e>0 is any constant. Prior to our work, the problem was open even...

The local ratio framework introduced by Bar Yehuda and Evan in 1981 provides a unified framework for many approximation algorithms. Recently, the local ratio technique has been used to provide efficient approximation algorithms for a number of...

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. I will show a general approach to deriving inapproximability results in the value oracle model, based on...

This work attempts to broaden the foundations of public-key cryptography. We construct a new public key encryption based on two “hardness on average” assumptions: (1) it is hard to “learn parity with noise” for random sparse equations; and (2) it is...

A halfspace (a.k.a. threshold) is a boolean function h : {-1,1}^n --> {-1,1} of the form h(x) = sign(w_0 + w_1 x_1 + ... + w_n x_n), where the weights w_i are arbitrary real numbers. Halfspaces are studied extensively in the theories of complexity...

I will discuss a lower bound of $\omega(n^(k/4))$ on the size of constant-depth $(AC_0)$ circuits solving the k-clique problem on n-vertex graphs. This bound follows from a stronger result that $AC_0$ circuits of size $O(n^(k/4))$ almost surely fail...

Via four applications: distribution modeling, probability estimation, data compression, and classification, we argue that when learning from data, discrete values should be ignored except for just their appearance-order pattern. Along the way, we...

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula F is a propositional formula in which each variable appears exactly once. Such a formula...

I will present a construction of an n-point negative type metric such that every t-point sub-metric is isometrically L1-embeddable, but embedding the whole metric into L1 incurs distortion at least k, where both t and k are (\log\log\log n)^{\Omega...

On Feb. 1, in his blog, Tim Gowers proposed an open collaboration on a math problem. Specifically, he suggested working on a combinatorial proof of the Density Hales-Jewett Theorem. This theorem states that for every delta > 0, if n is sufficiently...

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We...

Ideally, one would want to base the security of standard cryptographic primitives (such as pseudorandom generators) on widely believed worst-case complexity assumptions like P does not equal NP. However, it is currently not known if this is possible...

I will talk about a recent work describing a deterministic polynomial time algorithm for blackbox identity testing for depth three circuits with bounded top fanin over the field of rational numbers. This resolves a question posed by Klivans and...

Constraint Satisfaction Problems appear everywhere. The study of their quantum analogues (in which the constraints no longer commute), has become a lively area of study, and various recent results provide interesting insights into quantum physics...

A PCP is a proof system in which the proofs that can be verified by a verifier that reads only a very small part of the proof. One line of research concerning PCPs is trying to reduce their soundness error (i.e., the probability of accepting false...

An XOR game is a very simple model of evaluating a distributed function f(x,y) . With probability p(x,y) a Verifier sends questions x, y to Alice and Bob, respectively. Without communicating, Alice and Bob then output a, b in {-1,+1} in the hope...

Sex has been called "the queen of problems in evolutionary biology" since it is pervasive in nature yet its functional significance has not been known. It has often been assumed that the shuffling of genes due to sex is an adaptation that...

Research in the area of privacy of data analysis has been flourishing recently, with a rigorous notion such as differential privacy regarding the desired level of privacy and sanitizing algorithms matching the definition for many problems. Most of...

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem. The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to...

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential...