Publications

The Rate-Immediacy Barrier in Explicit Tree Code Constructions
Gil Cohen, Leonard J. Schulman, Piyush Srivastava
manuscript
download (ECCC)


A Study of Error Reduction Polynomials
Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz
manuscript
download (ECCC)


Tight Bounds for the Zig Zag Product
Gil Cohen, Itay Cohen, Gal Maor
FOCS 2024
download (ECCC)
Talk at IAS - part 1 & part 2
My uninvited talk on this paper
Slides from Dagstuhl


Derandomized Squaring: An Analytic Insight into Its True Behavior
Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled
ITCS 2025 (to appear)
download (ECCC)


Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries
Gil Cohen, Tal Yankovitz
CCC 2024 (to appear)
download (ECCC)
Tal's talk at Simons Berekeley


Spectral Expanding Expanders
Gil Cohen, Itay Cohen
CCC 2023
download (ECCC)


Random Walks on Rotating Expanders
Gil Cohen, Gal Maor
STOC 2023
download (ECCC)
slides


Approximating Iterated Multiplication of Stochastic Matrices in Small Space
This paper subsumes the manuscript "Approximating Large Powers of Stochastic Matrices in Small Space".
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
STOC 2023 (soft merge with this paper by Aaron (Louie) Putterman and Edward Pyne)
download (ECCC)
Dean's talk at IAS


Seed Protecting Extractors
Gil Cohen, Dean Doron, Shahar Samocha
Accepted to Theory of Computing (ToC)
download (ECCC)


Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
Gil Cohen, Tal Yankovitz
FOCS 2022
download (ECCC)


LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation
Gil Cohen, Tal Yankovitz
ICALP 2022
download (ECCC)
Tal's video at ICALP (first talk of the session.)


Expander Random Walks: The General Case and Limitations
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
ICALP 2022
download (ECCC)
slides
video at ICALP (begins at minute 28)


Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet
Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz
STOC 2022
download (ECCC)
Inbar's slides


Candidate Tree Codes via Pascal Determinant Cubes
Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan
RANDOM 2021
download (ECCC)
Inbar's talk at RANDOM


Error Reduction For Weighted PRGs Against Read Once Branching Programs
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma
CCC 2021
Ori's video at CCC
download (ECCC)
download (CCC)
slides


Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC
Gil Cohen, Tal Yankovitz
CCC 2021
download (ECCC)
download(CCC)
video at HUJI
Tal's talk at CCC
slides


Expander Random Walks: A Fourier-Analytic Approach
Gil Cohen, Noam Peri, Amnon Ta-Shma
STOC 2021
download (ECCC)
slides
video at IAS
Noam's talk at STOC 


Palette-Alternating Tree Codes
Gil Cohen, Shahar Samocha
CCC 2020
download (ECCC)
download (CCC)
video of Shahar at CCC


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
download (ECCC)
video at IAS (most recommended from my talks below)
video from BIRS CMO
video of Leonard at TCS+
video of Leonard at IIAS
Gil Kalai's post
slides


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
download (ECCC)
video at The Hebrew University
slides
far better slides
Goldreich's take
 
 
Towards Optimal Two-Source Extractors and Ramsey Graphs
Gil Cohen
STOC 2017
download (ECCC)
slides
poster
 
 
Making the Most of Advice: New Correlation Breakers and Their Applications 
Gil Cohen
FOCS 2016
download (ECCC)
slides
 
 
Extractors for Near Logarithmic Min-Entropy
Gil Cohen, Leonard Schulman
FOCS 2016
Invited to Theory of Computing (ToC) 2016
Invited to the SICOMP Special Issue for FOCS 2016 (regretfully declined)
download (ECCC)
slides
 
 
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
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)
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
 
 
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 The 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
 
 
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



Old manuscripts

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
Manuscript 2016
download (ECCC)


Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes
Gil Cohen, Amnon Ta-Shma
Manuscript 2013
download (ECCC)
slides


Gradual Small-Bias Sample Spaces
Avraham Ben-Aroya, Gil Cohen
Manuscript 2012
download (ECCC)
slides