Gil's Homepage

My Picture
Hi! I've just completed my Ph.D. at Weizmann Institute of Science under the advisement of Ran Raz. I'm expected to join Caltech as a CMI postdoctoral fellow in few months. I'm interested in many aspects of theoretical computer science, with focus on pseudo-randomness, and related mathematics. Please contact me for any question. My mail is my last name followed by g@gmail.com.

Algebraic Geometry for Theoretical Computer Science

I've delivered a course at Weizmann, entitled Algebraic Geometry for Theoretical Computer Science. More information can be found on the course web page.

Publications

  1. Gil Cohen
    Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
    Manuscript
    [Pdf]

  2. Gil Cohen, Igor Shinkar
    The Complexity of DNF of Parities
    Manuscript
    [Pdf]

  3. Gil Cohen, Amnon Ta-Shma
    Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes
    Manuscript
    [Pdf] [Slides]

  4. Avraham Ben-Aroya, Gil Cohen
    Gradual Small-Bias Sample Spaces
    Manuscript
    [Pdf] [Slides]

  5. Gil Cohen
    Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
    FOCS 2015
    [Pdf] [Slides]

  6. Gil Cohen, Avishay Tal
    Two Structural Results for Low Degree Polynomials and Applications
    RANDOM 2015
    [Pdf] [Video of Avishay at IAS]

  7. Gil Cohen, Igor Shinkar
    Zero-Fixing Extractors for Sub-Logarithmic Entropy
    ICALP 2015
    [Pdf] [Slides]

  8. Itai Benjamini, Gil Cohen, Igor Shinkar
    Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
    To appear in Israel Journal of Mathematics (preliminary version in FOCS 2014)
    [Pdf] [Slides] [Video at IAS] [Shorter video from FOCS]

  9. Gil Cohen, Anat Ganor, Ran Raz
    Two Sides of the Coin Problem
    RANDOM 2014
    [Pdf] [Slides]

  10. Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum
    Efficient Multiparty Protocols via Log-Depth Threshold Formulae
    CRYPTO 2013
    [Pdf] [Slides]

  11. Noga Alon, Gil Cohen
    On Rigid Matrices and U-Polynomials
    To appear in CC (preliminary version in CCC 2013)
    [Pdf] [Slides]

  12. Gil Cohen, Ran Raz, Gil Segev
    Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification
    SICOMP 2014 (preliminary version in CCC 2012)
    [Pdf] [Slides]

  13. Gil Cohen, Amir Shpilka, Avishay Tal
    On the Degree of Univariate Polynomials Over the Integers
    COMBINATORICA 2014 (preliminary version in ITCS 2012)
    [Pdf] [Slides]


Miscellaneous

  1. Lecture notes for a course I delivered at Weizmann
    A Taste of Circuit Complexity Pivoted at NEXP not in ACC (and more)
    Winter 2012/3
    [Pdf] [Course Blog]

  2. Ph.D. Thesis
    New Constructions and Applications of Pseudorandom Objects
    Under the guidance of Ran Raz, Weizmann Institute of Science, 2015
    [Pdf] [Slides from my Ph.D. festive talk]

  3. M.Sc. Thesis
    On the Degree of Symmetric Functions on the Boolean Cube
    Under the guidance of Amir Shpilka, Technion, 2010
    [Pdf] [Slides]

webs counters
visitors since July 14 2015