Publications

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Gil Cohen, Shahar Samocha

Manuscript

download (ECCC)

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

download (ECCC)

download (RANDOM)

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Gil Cohen, Bernhard Haeupler, Leonard Schulman

STOC 2018

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

download (ECCC)

video at IAS (most recommended from my talks below)

Short video from STOC

video from BIRS CMO

video of Leonard at TCS+

video of Leonard at IIAS

Gil Kalai's post

slides

Hitting Sets 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)

download (ECCC)

slides

Goldreich's take

 

 

Towards Optimal Two-Source Extractors and Ramsey Graphs

Gil Cohen

STOC 2017

download (ECCC)

video from STOC

slides

poster

 

 

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

Gil Cohen

FOCS 2016

download (ECCC)

video from FOCS

slides

 

 

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)

download (ECCC)

video from FOCS

slides

 

 

Non-Malleable Extractors with Logarithmic Seeds

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

Gil Cohen

download (ECCC)

 

 

Non-Malleable Extractors - New Tools and Improved Constructions

Gil Cohen

CCC 2016

download (ECCC)

slides

 

 

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

Gil Cohen

STOC 2016

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

download (ECCC)

video at IAS part 1 (one hour slides)

video at IAS part 2 (two hours board talk)

slides from STOC

Goldreich's take

a eureka moment

 

 

The Complexity of DNF of Parities

Gil Cohen, Igor Shinkar

ITCS 2016

download (ECCC)

 

 

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

Gil Cohen

SICOMP 2016 (preliminary version in FOCS 2015)

download (ECCC)

download (SICOMP)

video from FOCS

slides

Goldreich's take

 

 

Two Structural Results for Low Degree Polynomials and Applications

Gil Cohen, Avishay Tal

RANDOM 2015

download (ECCC)

video of Avishay at IAS

 

 

Zero-Fixing Extractors for Sub-Logarithmic Entropy

Gil Cohen, Igor Shinkar

ICALP 2015

download (ECCC)

slides

Goldreich's take

 

 

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

Itai Benjamini, Gil Cohen, Igor Shinkar

Israel Journal of Mathematics (preliminary version in FOCS 2014)

download (ECCC)

download (Israel Journal of Mathematics)

video at IAS

shorter video from FOCS

slides

Goldreich's take

Viola's take and context

 

 

Two Sides of the Coin Problem

Gil Cohen, Anat Ganor, Ran Raz

RANDOM 2014

download (ECCC)

slides

 

 

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Gil Cohen, Amnon Ta-Shma

Manuscript

download (ECCC)

slides

 

 

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

download (ECCC)

video of Ron at Simons Institute, Berkeley.

slides

Goldreich's take

 

 

On Rigid Matrices and U-Polynomials

Noga Alon, Gil Cohen

Computational Complexity 2015 (preliminary version in CCC 2013)

download (ECCC)

download (Computational Complexity)

slides

 

 

Gradual Small-Bias Sample Spaces

Avraham Ben-Aroya, Gil Cohen

Manuscript

download (ECCC)

slides

 

 

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

Gil Cohen, Ran Raz, Gil Segev

SICOMP 2014 (preliminary version in CCC 2012)

download (ECCC)

download (SICOMP)

slides

 

 

On the Degree of Univariate Polynomials Over the Integers

Gil Cohen, Amir Shpilka, Avishay Tal

COMBINATORICA 2016 (preliminary version in ITCS 2012)

download (ECCC)

download (COMBINATORICA)

slides

Theses

Ph.D. Thesis

New Constructions and Applications of Pseudorandom Objects

Under the guidance of Ran Raz, Weizmann Institute of Science, 2015

download

slides

M.Sc. Thesis

On the Degree of Symmetric Functions on the Boolean Cube

Under the guidance of Amir Shpilka, Technion, 2010

download