Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GIL COHEN:
All reports by Author Gil Cohen:

TR24-090 | 12th May 2024
Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

A Study of Error Reduction Polynomials

Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, ... more >>>


TR24-089 | 8th May 2024
Gil Cohen, Itay Cohen, Gal Maor

Tight Bounds for the Zig-Zag Product

The Zig-Zag product of two graphs, $Z = G \circ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of ... more >>>


TR23-183 | 24th November 2023
Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled

Derandomized Squaring: An Analytical Insight into Its True Behavior

The notion of the derandomized square of two graphs, denoted as $G \circ H$, was introduced by Rozenman and Vadhan as they rederived Reingold's Theorem, $\mathbf{SL} = \mathbf{L}$. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and ... more >>>


TR23-110 | 25th July 2023
Gil Cohen, Tal Yankovitz

Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

Revisions: 1

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>


TR22-163 | 16th November 2022
Gil Cohen, Gal Maor

Random Walks on Rotating Expanders

Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As ... more >>>


TR22-154 | 6th November 2022
Gil Cohen, Itay Cohen

Spectral Expanding Expanders

Dinitz, Schapira, and Valadarsky (Algorithmica 2017) introduced the intriguing notion of expanding expanders -- a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only ... more >>>


TR22-149 | 7th November 2022
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>


TR22-045 | 4th April 2022
Gil Cohen, Tal Yankovitz

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted ... more >>>


TR22-008 | 14th January 2022
Gil Cohen, Dean Doron, Ori Sberlo

Approximating Large Powers of Stochastic Matrices in Small Space

Comments: 1

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>


TR21-154 | 10th November 2021
Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz

Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and $(\log n)^{e}$ colors for some constant $e > 1$ that depends on the distance, where $n$ is ... more >>>


TR21-136 | 13th September 2021
Gil Cohen, Tal Yankovitz

LCC and LDC: Tailor-made distance amplification and a refined separation

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a ... more >>>


TR21-091 | 29th June 2021
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Expander Random Walks: The General Case and Limitations

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>


TR21-020 | 15th February 2021
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Error Reduction For Weighted PRGs Against Read Once Branching Programs

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>


TR20-163 | 5th November 2020
Gil Cohen, Noam Peri, Amnon Ta-Shma

Expander Random Walks: A Fourier-Analytic Approach

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>


TR20-161 | 5th November 2020
Gil Cohen, Dean Doron, Shahar Samocha

Seed Protecting Extractors

We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{Ext}(X,A(Y))$ for every choice of $A \in ... more >>>


TR20-141 | 11th September 2020
Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

Candidate Tree Codes via Pascal Determinant Cubes

Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>>


TR20-084 | 31st May 2020
Gil Cohen, Tal Yankovitz

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

Revisions: 1

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>


TR20-014 | 16th February 2020
Gil Cohen, Shahar Samocha

Palette-Alternating Tree Codes

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>


TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 2 , Comments: 1

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>


TR18-066 | 8th April 2018
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

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

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>


TR18-032 | 14th February 2018
Gil Cohen, Bernhard Haeupler, Leonard Schulman

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Revisions: 1

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>


TR17-161 | 30th October 2017
Mark Braverman, Gil Cohen, Sumegha Garg

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

Revisions: 1

Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2{n} + \log{n} \cdot \log(1/\varepsilon))$. A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal $O(\log{n}+\log(1/\varepsilon))$, or to construct improved hitting sets, as ... more >>>


TR16-114 | 30th July 2016
Gil Cohen

Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

Revisions: 1

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>


TR16-052 | 7th April 2016
Gil Cohen

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

Revisions: 1

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>>


TR16-030 | 7th March 2016
Gil Cohen

Non-Malleable Extractors with Logarithmic Seeds

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>


TR16-014 | 3rd February 2016
Gil Cohen, Leonard Schulman

Extractors for Near Logarithmic Min-Entropy

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an ... more >>>


TR15-183 | 16th November 2015
Gil Cohen

Non-Malleable Extractors - New Tools and Improved Constructions

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>


TR15-095 | 14th June 2015
Gil Cohen

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $2\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>>


TR15-038 | 11th March 2015
Gil Cohen

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

Revisions: 1

We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables ... more >>>


TR14-160 | 27th November 2014
Gil Cohen, Igor Shinkar

Zero-Fixing Extractors for Sub-Logarithmic Entropy

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = ... more >>>


TR14-099 | 7th August 2014
Gil Cohen, Igor Shinkar

The Complexity of DNF of Parities

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>


TR14-023 | 19th February 2014
Gil Cohen, Anat Ganor, Ran Raz

Two Sides of the Coin Problem

Revisions: 1

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>


TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>


TR13-145 | 20th October 2013
Gil Cohen, Avishay Tal

Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>


TR13-138 | 5th October 2013
Itai Benjamini, Gil Cohen, Igor Shinkar

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

Revisions: 1

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>


TR13-107 | 7th August 2013
Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

Efficient Multiparty Protocols via Log-Depth Threshold Formulae

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves
security against a single corrupted party. Such protocols are typically easy
to construct as they may employ techniques that do not ... more >>>


TR12-133 | 21st October 2012
Noga Alon, Gil Cohen

On Rigid Matrices and Subspace Polynomials

Revisions: 1

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>


TR12-050 | 25th April 2012
Avraham Ben-Aroya, Gil Cohen

Gradual Small-Bias Sample Spaces

Revisions: 3

A $(k,\epsilon)$-biased sample space is a distribution over $\{0,1\}^n$ that $\epsilon$-fools every nonempty linear test of size at most $k$. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.

When ... more >>>


TR11-096 | 2nd July 2011
Gil Cohen, Ran Raz, Gil Segev

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

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>


TR11-002 | 9th January 2011
Gil Cohen, Amir Shpilka, Avishay Tal

On the Degree of Univariate Polynomials Over the Integers

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>


TR10-039 | 10th March 2010
Gil Cohen, Amir Shpilka

On the degree of symmetric functions on the Boolean cube

Comments: 1

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in
\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our
result shows a surprising ... more >>>




ISSN 1433-8092 | Imprint