Theoretical Computer Science and Discrete Mathematics

The Permanents of Gaussian Matrices

Scott Aaronson
Massachusetts Institute of Technology
November 29, 2010

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial hierarchy collapses. Several optics groups are already working toward doing our experiment.

Self-Correction, Distance Estimation and Local Testing of Codes

Dana Moshkovitz
Massachusetts Institute of Technology
November 29, 2010

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 $c$, and an index $i\in [n]$ to correct, with high probability over $i$ and over the internal randomness, the local algorithm returns a list of possible corrections that contains $c_i$.

Introduction to the Coq Proof Assistant

Andrew Appel
Princeton University
December 7, 2010

A "proof assistant" is a software package comprising a validity checker for proofs in a particular logic, accompanied by semi-decision procedures called "tactics" that assist the mathematician in filling in the easy parts of the proofs. I will demonstrate the use of the Coq proof assistant in doing simple proofs about inductive structures such as natural numbers, sequences, and trees.

Colouring Tournaments

Paul Seymour
Princeton University
December 13, 2010

A ``tournament'' is a digraph obtained from a complete graph by directing its edges, and ``colouring'' a tournament means partitioning its vertex set into acyclic subsets (``acyclic'' means the subdigraph induced on the subset has no directed cycles). This concept is quite like that for graph-colouring, but different. For instance, there are some tournaments H such that every tournament not containing H as a subdigraph has bounded chromatic number. We call them ``heroes''; for example, all tournaments with at most four vertices are heroes.

Learning with Boolean Threshold Functions, a Statistical Physics Perspective

Rémi Monasson
Ecole Normale Superieure; Simons Center for Systems Biology, IAS
January 25, 2011

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered systems to characterize BTF in a quantitative way [1], with an emphasis on computational and geometrical aspects. These techniques will be illustrated on two particular cases: the celebrated perceptron (Linear Threshold Function) [2], and the more realistic tempotron model of a neuron [3,4].

Pages