Seminars Sorted by Series

Computer Science/Discrete Mathematics Seminar II

Dec
07
2004

Computer Science/Discrete Mathematics Seminar II

Variance/Entropy Decomposition Techniques for Proving Fast Mixing of the Glauber Dynamics
10:30am|S-101

The Glauber dynamics is a simple Markov chain algorithm for sampling from distributions that arise in models from statistical physics. In each step of this dynamics the value (or spin) of a random site is updated according to some rule which is...

Dec
14
2004

Computer Science/Discrete Mathematics Seminar II

Variance/Entropy Decomposition Techniques for Proving Fast Mixing of the Glauber Dynamics
10:30am|S-101

The Glauber dynamics is a simple Markov chain algorithm for sampling from distributions that arise in models from statistical physics. In each step of this dynamics the value (or spin) of a random site is updated according to some rule which is...

Jan
18
2005

Computer Science/Discrete Mathematics Seminar II

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
10:30am|S-101

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed...

Jan
25
2005

Computer Science/Discrete Mathematics Seminar II

The Tic-Tac-Toe Theory
Jozsef Beck
10:30am|S-101

I want to show proofs for two things: (1) what kind of complicated structures can a player build in a "generalized Tic-Tac-Toe game", and (2) how to get the "exact solutions" of infinitely many games. I'll try to illustrate the ideas on simple...

Feb
01
2005

Computer Science/Discrete Mathematics Seminar II

Geometric symmetrizations in high dimension
10:30am|S-101

A classical method for proving geometric inequalities in which the Euclidean ball is the extremal case, is that of symmetrization. The idea is basically to perform a simple operation on a given convex body in n-dimensional space, which makes it more...

Feb
08
2005

Computer Science/Discrete Mathematics Seminar II

Forcing with Random Variables
10:30am|S-101

The links between propositional proof systems and bounded arithmetic (a generic name for a collection of first-order theories of arithmetic) have many facets but informally one can view them as two sides of the same thing: The former is a non...

Feb
15
2005

Computer Science/Discrete Mathematics Seminar II

Fixed Point Properties of Random Groups
10:30am|S-101

In a sequence of preprints M. Gromov introduced a new model of a random quotient of a finitely generated group and indicated that under favourable conditions the quotient groups should be non-trivial and satisfy Kazhdan's Property (T), both with...

Feb
22
2005

Computer Science/Discrete Mathematics Seminar II

Quadratic Forms on Graphs
Konstantin Makarychev
10:30am|S-101

We introduce a new graph parameter, called the rothendieck constant of a graph. This parameter is a generalization of the classical Grothendieck constant; and it is equal to an integrality gap of a certain SDP problem, which has various algorithmic...

Mar
01
2005

Computer Science/Discrete Mathematics Seminar II

Pseudorandom Walks in Biregular Graphs and the RL vs. L. Problem
10:30am|S-101

In this talk, we will discuss additional details of the `SL=L' result, not covered by the first talk. We will focus, however, on the possibility of extending our techniques towards resolving the general RL vs. L question. In this direction we obtain...

Mar
08
2005

Computer Science/Discrete Mathematics Seminar II

Excited Random Walk
10:30am|S-101

Excited random walk is a process on Z^d which behaves like a regular balanced random walk when it reaches a vertex it already visited, but when it reaches a new vertex it has a drift to the right. We shall review a number of new results about this...

Mar
15
2005

Computer Science/Discrete Mathematics Seminar II

Gems of Combinatorial Number Theory
10:30am|S101

We describe four theorems from Combinatorial Number Theory, and sketch their proofs (as time permits). These theorems were important to the recent extractors and Ramsey graphs obtained in [Barak-Impagliazzo-Wigderson] and [Barak-Kindler-Sudakov...

Mar
22
2005

Computer Science/Discrete Mathematics Seminar II

1 Dimensional Diffusion Limited Aggregation (DLA)
Gideon Amir
10:30am|S-101

In a paper from 1981 Sanders and Witten introduced the (2-Dim) DLA process --- a stochastic growth model, in which a "Discrete fractal" subset of $Z^2$ is grown from the origin in an inductive process, where in each step a particle, starting at...

Mar
29
2005

Computer Science/Discrete Mathematics Seminar II

Controlled Linear Programming and Linear Complementarity for Some Infinite Games in NP $\cap$ coNP
Sergei Vorobyov
10:30am|S-101

We present the Controlled Linear Programming Problem (CLPP), a new combinatorial optimization problem nicely merging linear programming with games. In a system of linear monotone constraints of the form $x_i\leq p_i^j(\bar x)+w_i^j$, where $p_i^j$...

Apr
05
2005

Computer Science/Discrete Mathematics Seminar II

Even Hole Free Graphs
10:30am|S-101

A graph is called {\em even-hole-free} if no induced subgraph of it is a cycle with an even number of vertices. A vertex of a graph is {\em bisimplicial} if the vertex set of its neighborhood can be partitioned into two cliques. Bruce Reed...

Apr
12
2005

Computer Science/Discrete Mathematics Seminar II

Cuts, Quadratic Programs and in Between
Muli Safra
10:30am|S-101

We study the following problem regarding quadratic programs: Given a quadratic polynomial \sum a_{xy} xy, where all a_{xx} = 0, find a -1,+1 assignment to its variables that maximizes it. This problem recently attracted attention due to its...

Apr
19
2005

Computer Science/Discrete Mathematics Seminar II

Additive Approximation for Edge-Deletion Problems
10:30am|S-101

I will sketch a proof that for any monotone graph property P and any $\epsilon >0$ one can approximate efficiently the minimum number of edges that have to be deleted from an n-vertex input graph to get a graph that satisfies P, up to an additive...

Apr
26
2005

Computer Science/Discrete Mathematics Seminar II

Lower Bounds for the Noisy Broadcast Problem
Navin Goyal
10:30am|S-101

One of the simplest and fundamental distributed computing problems involving noise is the ``noisy broadcast problem'': There are n processors each holding a bit, and there is a special processor called receiver. Processors act according to a...

May
03
2005

Computer Science/Discrete Mathematics Seminar II

Extremal Erodos-Szekeres Permutations and Square Young Tableaux
Dan Romik
10:30am|S-101

An Extremal Erdos-Szekeres permutation is a permutation of the numbers 1,2,...,N^2 that has no monotone subsequence of length N+1 (and is therefore extremal with respect to the Erdos-Szekeres theorem). If an EES permutation is drawn uniformly at...

May
31
2005

Computer Science/Discrete Mathematics Seminar II

Approximation Algorithms for Unique Games
11:30am|S-101

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is...

Sep
27
2005

Computer Science/Discrete Mathematics Seminar II

Property Tau and the Product Replacement Algorithm
Alex Lubotzky
10:30am|S-101

The product replacement algorithm is a commonly used algorithm to generate a random element in a finite group. While its performance is quite outstanding, its theretical understanding is quite poor. We will present a joint work with Igor Pak (JAMS...

Nov
01
2005

Computer Science/Discrete Mathematics Seminar II

Expander Graphs on the Symmetric Groups
10:30am|S-101

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

Nov
08
2005

Computer Science/Discrete Mathematics Seminar II

Expander Graphs on the Symmetric Groups, Part II
10:30am|S-101

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

Nov
22
2005

Computer Science/Discrete Mathematics Seminar II

Euclidean Embeddings of Finite Metric Spaces: Distortion and Expansion
10:30am|S-101

Bi-lipschitz embeddings of finite metric spaces into Hilbert space have become an increasingly important tool in discrete mathematics and theoretical computer science. For example, this theory is intimately related to the algorithmic problem of...

Nov
29
2005

Computer Science/Discrete Mathematics Seminar II

Szemeredi's Regularity Lemma in Analysis
10:30am|S-101

We give three different analytic interpretations of Szemeredi's famous Regularity Lemma. The first one is a general statement about Hilbert spaces. The second one presents the Regularity Lemma as the compactness of a certain metric space. The third...

Dec
06
2005

Computer Science/Discrete Mathematics Seminar II

Coding Theory: Survey of Recent Progress and Open Questions
Madhu Sudan
10:30am|S-101

Coding theory emerged in the late 1940's, thanks to the works of Shannon and Hamming, as the theory supporting "reliable transmission of information (in the presence (fear?) of noise)". More than fifty years since, enormous progress has been made...

Dec
13
2005

Computer Science/Discrete Mathematics Seminar II

Dependent Random Choice and Extremal Problems
Benny Sudakov
10:30am|S-101

The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics and it belongs to those areas of mathematical research that have experienced a most impressive growth in recent years. One of the parts of discrete mathematics...

Jan
17
2006

Computer Science/Discrete Mathematics Seminar II

Szemeredi's Regularity Lemma and Compactness
10:30am|S-101

We introduce a metric space which is the closure of the isomorphism classes of graphs in a natural topology. It turns out that the regularity lemma is equivalent with the compactness of this space. We present applications, open questions, and...

Jan
24
2006

Computer Science/Discrete Mathematics Seminar II

Random Discrete Matrices: A Survey
10:30am|S-101

Random matrices is a large area in mathematics, with connections to many other areas, such as mathematical physics, combinatorics, and theoretical computer sience, to mention a few. There are, by and large, two kinds of random matrices. The first...

Jan
31
2006

Computer Science/Discrete Mathematics Seminar II

Cryptography and the P vs NP Question
10:30am|S-101

A fundamental question in cryptography is whether the existence of hard on average problems can be based solely on the assumption that P not equal to NP (more precisely, NP not in BPP). The commonly held belief that average-case hardness requires...

Feb
14
2006

Computer Science/Discrete Mathematics Seminar II

Quantum Computing and Finite Permutation Groups
Aner Shalev
10:30am|S-101

We shall discuss Quantum Computing, and the so called Hidden Subgroup Problem, which in the abelian case was the basis for Shor's celebrated factorization algorithm. The solution for non-abelian groups, and symmetric groups in particular, is one of...

Feb
28
2006

Computer Science/Discrete Mathematics Seminar II

Independent Transversals in Locally Sparse Graphs
Po-Shen Loh
10:30am|S-101

Let $G$ be a graph with maximum degree $\Delta$ whose vertex set is partitioned into $r$ parts $V(G)=V_1 \cup \ldots \cup V_r$. An independent transversal is an independent set in $G$ which contains exactly one vertex from each $V_i$. The problem of...

Mar
07
2006

Computer Science/Discrete Mathematics Seminar II

Strong Approximation in Random Towers of Graphs
10:30am|S-101

Random covers of graphs, and random group actions on rooted trees, are different languages, that describe the same phenomenon. The former were studied by Amit, Linial. Matousek, Bilu. The latter were studied by Abert and Virag. Let T(n) be a binary...

Mar
14
2006

Computer Science/Discrete Mathematics Seminar II

Group Theoretic Algorithms For Fast matrix Multiplication
Balazs Szedgedy
10:30am|S-101

In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using only 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and...

Mar
28
2006

Computer Science/Discrete Mathematics Seminar II

The Grothendieck Constant of an Expander
10:30am|S-101

The Grothendieck constant of a graph is an invariant whose study, which is motivated by algorithmic applications, leads to several extensions of a classical inequality of Grothendieck. This invariant was introduced in a joint paper with Makarychev...

Apr
04
2006

Computer Science/Discrete Mathematics Seminar II

Periodic Orbits and Extractors
10:30am|S-101

We consider periodic orbits of multiparameter diagonalizable actions. A simple example of such an action is the action generated by the maps x -> 2x mod 1 and x -> 3x mod 1 on R/Z. There are strong parallels between the study of these orbits and...

Apr
11
2006

Computer Science/Discrete Mathematics Seminar II

New Techniques in Online Game Playing
Elad Hazan
10:30am|S-101

We introduce a new algorithm and a new analysis technique that is applicable to a variety of online optimization scenarios, including regret minimization for Lipschitz regret functions, universal portfolio management, online convex optimization and...

Apr
18
2006

Computer Science/Discrete Mathematics Seminar II

Black Boxes, Inc.
10:30am|S-101

I will survey a number of settings withing theoretical computer sceince in which certain computations are abstracted by "black boxes", namely devices for which we can observe the input-output behavior, but not the actual "guts" of the computation. I...

May
02
2006

Computer Science/Discrete Mathematics Seminar II

On the Minimal Density of Triangles in Graphs
10:30am|S-101

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

May
09
2006

Computer Science/Discrete Mathematics Seminar II

On the Minimal Density of Triangles in Graphs (continued)
10:30am|S-101

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

May
16
2006

Computer Science/Discrete Mathematics Seminar II

Randomness Reduction in Some Results of Asympotic Geometric Analysis
Shiri Artstein
10:30am|Dilworth Room

I will describe some recent results joint with V. Milman in which we take the computer science approach to derandomization and apply it in questions from asymptotic geometric analysis. The special type of questions requires an adaptation of the...

Sep
19
2006

Computer Science/Discrete Mathematics Seminar II

The Sum-Product Theorem and Applications
10:30am|S-101

About two years ago Bourgain, Katz and Tao proved that in every finite field, a set which does not grow "much" when we add all pairs of elements, and when we multiply all pairs of elements, must be very "close" to a subfield. This theorem revealed...

Sep
26
2006

Computer Science/Discrete Mathematics Seminar II

Sum-Product Theorem in Finite Fields (Continued)
10:30am|S-101

While a continuation of last week's lecture, I'll try to make it self contained. I will describe some of the ideas and tools used in the proof of the Sum-Product theorem. I will describe a statistical version, and its use in extractor construction.

Oct
03
2006

Computer Science/Discrete Mathematics Seminar II

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
10:30am|S-101

In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to...

Oct
10
2006

Computer Science/Discrete Mathematics Seminar II

An Invitation to Combinatorial Games
10:30am|West Building Lecture Theatre

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed...