Seminars Sorted by Series

We shall revisit the Boltzmann equation for rarefied non-linear particle dynamics, of conservative or dissipative nature, and on the stochastic N-particle model, introduced by M. Kac [19]. Related to this equation, we consider a a probabilistic...

In this talk, we have two subjects. I. Partial toroidal compactifications and moduli of PLH. II. The eight enlargements of Griffiths domain D and the fundamental diagram. For I, we have Theorem. For a given pair of global monodromy and fan, there...

Main conjectures of (log) MMP are: A) existence of flips, B) termination of flips, and C) finite generation, all of which were settled by 1992 in dim 3 by Mori, Shokurov, Kawamata, Koll\'ar et al. In dim 4, A was done by 2005 due to Shokurov and...

The method of multiplier ideals is one of the most versatile tools to study singularities of varieties. For the local theory, we present a connection between multiplier ideals and D-modules based on joint work with M. Mustata and M. Saito which has...

On a topological space, algebraic topology and homological algebra endow cohomology groups with various filtrations. In the case of algebraic varieties, one may wonder if such filtrations, e.g. the Grothendieck filtration, the Leray filtration, the...

First we define, for any analytic manifold $X$ of dimension $n$, locally residual currents; $C^{q,p}$ denotes the sheaf of locally residual currents of bidegree $(q,p)$. Then, we have a fundamental resolution of the sheaf of holomorphic $q-$forms $...

In Lafforgue's proof of the Langlands conjecture for GL(2) over a functional field, an important step is to compactify the moduli spaces of Drinfeld's shtukas. In this talk, I will present a new approach to this problem using the Geometric Invariant...

I will give an introduction to spaces of jets of algebraic varieties, explining their relevance for birational geometry. In particular, I will explain why these spaces are useful in the study of singularities.

In 1991, Witten proposed a famous conjecture (solved by Kontsevich) related the intersection theory of Deligne-Mumford moduli space to KDV-integrable hierearchy. To generalize his conjecture, Witten proposed a remarkable PDE based any...

Characteristic classes of Flat bundles on smooth algebraic varieties are defined in various cohomology theories. We consider the de Rham cohomology, the Deligne cohomology and the rational Chow groups and study the classes. We focus on the special...

The talk is based on the joint work with Boris Doubrov. First we will describe a new rather effective procedure of symplectification for the problem of local equivalence of nonholonomic vector distributions. The starting point of this procedure is...

Let $X\subset \P^N$ be a projective submanifold of dimension $n$ in the complex projective space $\P^N$. Let $U$ be a domain in the parameter space $T$ of complete intersections of codimension $m$ and of a given bidegree $(d_1,\dots,d_m)$ in $\P^N$...

Consider an arrangement of nonsingular subvarieties in a nonsingular algebraic variety. We define a compactification of the complement by replacing these subvarieties with a normal crossing divisor. This compactification is obtained by a sequence of...

Let $f:X\to Y$ be a projective map, and assume for simplicity $X$ to be smooth. The Decomposition Theorem of Beilinson, Bernstein, Deligne and Gabber states that the (derived direct image of the constant sheaf ${\bf Q}_X$ is isomorphic to a direct...

We'll start by exhibiting volume-minimizing properties for certain isotropic submanifolds in complex projective spaces via integral geometry. This will lead us to a problem of finding the infimum of areas for isotropic surfaces with a given boundary...

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries: 1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword...

Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to a special case of computing the unit group, but a reduction in the other direction is not...

A family of sets is called intersecting if the intersection of every two sets in the family is non empty. Many of the fundamental theorems in extremal set theory deal with the maximal size of an intersecting family under certain restrictions. A...

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given $n$ numbers, do any $r$ of them add up to $0$? His lower bound of $\Omega(n^{\lceil r/2...

We will describe definitions and algorithmic results for the ``census problem''. Informally, in a census individual respondents give private information to a trusted (and trustworthy) party, who publishes a sanitized version of the data. There are...

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw)...

In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new...

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer...

I will discuss some (very) recent results showing how techniques from the theory of Gaussian Hilbert spaces can be used in order to solve a number of open problems regarding boolean functions with low influences. I will survey some of the background...

The goal of hardness amplification is to take a function f : {0,1}^n --> {0,1} that is mildly average-case hard (i.e., very "small" circuit fails to compute f on at least a 1/poly(n) fraction of inputs), and produce a new function f' that is very...

We prove a number of general theorems about CZK, the class of problems possessing computational zero-knowledge proofs. Our results are *unconditional*, in contrast to most previous works on CZK which rely on the assumption that one-way functions...

I will present recent joint work with O. Friedland and V. Milman, where we use simple probabilistic estimates on Bernoulli random variables, together with tools from convex geometric analysis, to arrive at some new results. The first result has to...

The problem of average-case learning for decision trees is as follows: a decision tree T (over Boolean features x1,...,xn) is chosen at random from some natural distribution over decision trees. The learner is given access to uniform random examples...

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be...

We present new PCPs for NP-complete languages. The PCPs are only n poly log n bits long, when proving satisfiability of formulae of length n. However, the probabilistic verifier needs to query poly log n bits of the proof to verify it. In contrast...

A graph property P is said to be uniformly-testable if there is a property-tester for P that receives the error parameter \epsilon as part of the input, and whose query complexity is a function of \epsilon only. P is said to be non-uniformly...

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d>=2 and 0

The goal of Statistical Learning Theory is to construct and understand algorithms that are able to generalize from a given training data set. Statistical learning algorithms are wildly popular now due to their excellent performance on many types of...

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we consider the possibility of computing instances of these primitives by NC0 circuits, in...

Counting homomorphisms between graphs has a surprising number of applications. Many models in statistical mechanics and many questions in extremal graph theory can be phrased in these terms. We introduce a matrix, which we call the connection matrix...

Given a polytope P with a real-valued objective function f on its vertices, we consider the problem of finding a minima of f. Arguably the simplest randomized approach is the simplex algorithm RANDOMEDGE. Sitting at a vertex of P, RANDOMEDGE chooses...

In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. Traditional algorithms design assumes that the problem is described by a single objective function...

The well-known Max Cut problem asks for the largest bipartite subgraph of a graph G. This problem has been the subject of extensive research, both from the algorithmic perspective in computer science and the extremal perspective in combinatorics...

Given a hypergraph H=(V,E), its conflict-free chromatic number (CF-chromatic number) is the minimum number of colors needed to color the vertex set V such that, for every hyperedge S, there is at least one element v \in S whose color is unique (in S...

A ranking of n web pages is to be chosen from outputs of k search engines. How do we choose one ranking minimizing the "disagreement" with the k rankings? A clustering of n genes is to be chosen from outputs of k clustering algorithms. How do we...

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and...

We study the multicommodity buy-at-bulk network design problem where the goal is to buy capacity on edges of a network so as to enable the demands between a given set of source-sink pairs to be routed - the objective is to minimize the cost of such...

For an undirected graph G=(V,E), let G^n denote the graph whose vertex set is V^n in which two distinct vertices (u_1, u_2, ... ,u_n) and (v_1, v_2, ... ,v_n) are adjacent iff for all i between 1 and n, u_i and v_i are either equal or adjacent. The...

There has been substantial work in learning theory and game theory on adaptive "no-regret" algorithms for problems of repeated decision-making. For example, one could use such an algorithm to choose a path to drive to work each day so that no matter...