Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

Santosh Vempala
Georgia Institute of Technology
January 30, 2011
Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming.

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].

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.

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.

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$.