Screen Shot 2020-11-05 at 23.22.31.png

Expander Random Walks: A Fourier-Analytic Approach

Gil Cohen, Noam Peri, Amnon Ta-Shma

STOC 2021

Screen Shot 2020-11-05 at 23.20.03.png

Seed Protecting Extractors

Gil Cohen, Dean Doron, Shahar Samocha


Screen Shot 2020-09-20 at 12.16.08.png

Candidate Tree Codes via Pascal Determinant Cubes

Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan


Screen Shot 2020-09-20 at 12.28.49.png

Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

Gil Cohen, Tal Yankovitz


Screen Shot 2020-09-20 at 12.35.54.png

Palette-Alternating Tree Codes

Gil Cohen, Shahar Samocha

CCC 2020

Screen Shot 2020-09-20 at 12.51.17.png

Two-Source Condensers with Low Error and Low Entropy Gap via Entropy-Resilient Functions

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma


Screen Shot 2020-09-20 at 12.57.06.png

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Gil Cohen, Bernhard Haeupler, Leonard Schulman

STOC 2018

Screen Shot 2020-09-20 at 14.06.28.png

Pseudo-Random Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs

Mark Braverman, Gil Cohen, Sumegha Garg

STOC 2018

Invited to the SICOMP Special Issue for STOC 2018 (accepted)

Screen Shot 2020-09-20 at 14.10.16.png

Towards Optimal Two-Source Extractors and Ramsey Graphs

Gil Cohen

STOC 2017

Screen Shot 2020-09-20 at 14.14.15.png

Making the Most of Advice: New Correlation Breakers and Their Applications 

Gil Cohen

FOCS 2016

Screen Shot 2020-09-20 at 17.55.36.png

Extractors for Near Logarithmic Min-Entropy

Gil Cohen, Leonard Schulman

FOCS 2016

Invited to Theory of Computing (ToC) 2016 (accepted)

Invited to the SICOMP Special Issue for FOCS 2016 (regretfully declined)


Screen Shot 2020-09-20 at 18.03.40.png

Non-Malleable Extractors with Logarithmic Seeds

Gil Cohen


This paper has been subsumed by "Making the Most of Advice..." (see above) though this earlier manuscript is simpler and yields optimal non-malleable extractors (up to constants) for constant error.

Screen Shot 2020-09-20 at 18.06.36.png

Non-Malleable Extractors - New Tools and Improved Constructions

Gil Cohen

CCC 2016

Screen Shot 2020-09-20 at 18.10.14.png

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

Gil Cohen

STOC 2016

Invited to the SICOMP Special Issue for STOC 2016 (accepted)

Screen Shot 2020-09-20 at 18.24.20.png

The Complexity of DNF of Parities

Gil Cohen, Igor Shinkar

ITCS 2016

Screen Shot 2020-09-20 at 20.55.25.png

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Gil Cohen

FOCS 2015; SICOMP 2016

Screen Shot 2020-09-20 at 21.01.27.png

Two Structural Results for Low Degree Polynomials and Applications

Gil Cohen, Avishay Tal


Screen Shot 2020-09-20 at 21.04.05.png

Zero-Fixing Extractors for Sub-Logarithmic Entropy

Gil Cohen, Igor Shinkar

ICALP 2015

Screen Shot 2020-09-20 at 23.59.04.png

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Itai Benjamini, Gil Cohen, Igor Shinkar

FOCS 2014; Israel Journal of Mathematics 2016

Screen Shot 2020-09-21 at 0.02.02.png

Two Sides of the Coin Problem

Gil Cohen, Anat Ganor, Ran Raz


Screen Shot 2020-09-21 at 0.04.21.png

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Gil Cohen, Amnon Ta-Shma


Screen Shot 2020-09-21 at 9.30.14.png

Efficient Multiparty Protocols via Log-Depth Threshold Formulae

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

CRYPT0 2013

Screen Shot 2020-09-21 at 9.33.48.png

On Rigid Matrices and U-Polynomials

Noga Alon, Gil Cohen

CCC 2013; Computational Complexity 2015

Screen Shot 2020-09-21 at 9.35.43.png

Gradual Small-Bias Sample Spaces

Avraham Ben-Aroya, Gil Cohen


Screen Shot 2020-09-21 at 9.37.29.png

Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

Gil Cohen, Ran Raz, Gil Segev

CCC 2012; SICOMP 2014

Screen Shot 2020-09-21 at 9.39.56.png

On the Degree of Univariate Polynomials Over the Integers

Gil Cohen, Amir Shpilka, Avishay Tal