PAPErs

Screen Shot 2020-11-05 at 23.22.31.png

Expander Random Walks: A Fourier-Analytic Approach

Gil Cohen, Noam Peri, Amnon Ta-Shma

Manuscript

Screen Shot 2020-11-05 at 23.20.03.png

Seed Protecting Extractors

Gil Cohen, Dean Doron, Shahar Samocha

Manuscript

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

Manuscript

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

Manuscript

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

RANDOM 2019

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

Manuscript

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

RANDOM 2015

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

RANDOM 2014

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

Manuscript

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

Manuscript

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

ITCS 2012; COMBINATORICA 2016