Publications Palette-Alternating Tree Codes Note that this paper is a (significant) revision of a prior writeup "Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors" Gil Cohen, Shahar Samocha Manuscript 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 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) 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)
Towards Optimal Two-Source Extractors and Ramsey Graphs Gil Cohen STOC 2017
Making the Most of Advice: New Correlation Breakers and Their Applications Gil Cohen FOCS 2016
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)
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
Non-Malleable Extractors - New Tools and Improved Constructions Gil Cohen CCC 2016
Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs Gil Cohen STOC 2016 Invited to the SICOMP Special Issue for STOC 2016 (accepted)
The Complexity of DNF of Parities Gil Cohen, Igor Shinkar ITCS 2016
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers Gil Cohen SICOMP 2016 (preliminary version in FOCS 2015)
Two Structural Results for Low Degree Polynomials and Applications Gil Cohen, Avishay Tal RANDOM 2015
Zero-Fixing Extractors for Sub-Logarithmic Entropy Gil Cohen, Igor Shinkar ICALP 2015
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)
Two Sides of the Coin Problem Gil Cohen, Anat Ganor, Ran Raz RANDOM 2014
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes Gil Cohen, Amnon Ta-Shma Manuscript
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
On Rigid Matrices and U-Polynomials Noga Alon, Gil Cohen Computational Complexity 2015 (preliminary version in CCC 2013)
Gradual Small-Bias Sample Spaces Avraham Ben-Aroya, Gil Cohen Manuscript
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification Gil Cohen, Ran Raz, Gil Segev SICOMP 2014 (preliminary version in CCC 2012)
On the Degree of Univariate Polynomials Over the Integers Gil Cohen, Amir Shpilka, Avishay Tal COMBINATORICA 2016 (preliminary version in ITCS 2012)
Theses Ph.D. Thesis New Constructions and Applications of Pseudorandom Objects Under the guidance of Ran Raz, Weizmann Institute of Science, 2015 M.Sc. Thesis On the Degree of Symmetric Functions on the Boolean Cube Under the guidance of Amir Shpilka, Technion, 2010