# Computer Science and Discrete Mathematics (CSDM)

## Learning with Boolean Threshold Functions, a Statistical Physics Perspective

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

## Efficiently Learning Mixtures of Gaussians

## Cross-Validation and Mean-Square Stability

## Erdos Distinct Distance Problem in the Plane

Erdos conjectured that N points in the plane determine at least c N (log N)^{-1/2} different distances. Building on work of Elekes-Sharir, Nets Katz and I showed that the number of distances is at least c N (log N)^{-1} . (Previous estimates had lower bounds like N^{.86}.)

## Colouring Tournaments

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

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.

## Nonlinear Dvoretzky Theory

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any

## Hardness Escalation and the Rank of Polynomial Threshold Proofs

## Self-Correction, Distance Estimation and Local Testing of Codes

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