Description
Aviad Rubinstein
Satisfiability and Evolution
We show that, if truth assignments on n variables reproduce through recombination so that satisfaction of a particular Boolean function confers a small evolutionary advantage, then a poly-large population over poly-many generations (polynomial in n and the inverse of the initial satisfaction probability) will end up almost certainly consisting exclusively of satisfying truth assignments. We argue that this theorem sheds light on the problem of novelty in Evolution.
In the spirit of the seminar, I plan to speak at most 10~15 minutes about biology, and then move on to discuss the proof techniques, using Fourier analysis over the Boolean hypercube.
Based on joint works with Adi Livnat, Christos Papadimitriou, Greg Valiant, and Andrew Wan
Guy Kindler
Direct Sum Testing
The The k-fold direct sum encoding of a Boolean string w is the function f, such that on any set of coordinates S of size k, f returns the sum (mod 2) of the S-coordinates of w. Direct sums were considered in TCS for the purpose of hardness amplification in circuit complexity, and since then have been extensively studied. They can also potentially be used for gap amplification in PCP constructions, provided that we can devise and analyze local tests for them. We thus naturally arrive at the following problem: Efficiently test whether a function f is a k-fold direct sum encoding. In this work we define and analyze such a test.
This is joint work with Roee David, Irit Dinur, Elazar Goldenberg, and Igor Shinkar
All scheduled dates:
Upcoming
No Upcoming activities yet