School of Mathematics

"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consist

Menachem Kojman
Ben Gurion University of the Negev; Member, School of Mathemtics
April 6, 2011

MATHEMATICAL CONVERSATIONS

"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consistency." -- Andre Weil

General Hardness Amplification of Predicates and Puzzles

Grant Schoenbeck
Princeton University
March 29, 2011

In this talk, I will give new proofs for the hardness amplification of fficiently samplable predicates and of weakly verifiable puzzles. More oncretely, in the first part of the talk, I will give a new proof of Yao's XOR-Lemma as well as related theorems in the cryptographic setting. This proof seems simpler than previous ones, yet immediately generalizes to statements similar in spirit such as the extraction lemma used to obtain pseudo-random generators from one-way functions [Hastad, Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999].

Limit Theorems for the Möbius function Function and Statistical Mechanics

Francesco Cellarosi
Princeton University
March 29, 2011

I will present a recent joint work with Ya.G. Sinai. We investigate the ``randomness" of the classical Möbius function by means of a statistical mechanical model for square-free numbers and we prove some new results, including a non-standard limit theorem where the Dickman-De Bruijn distribution appears. Although we use a probabilistic approach, this work is inspired by a conjecture by P. Sarnak, and by a number of recent results relating Number Theory and Ergodic Theory.