Author name cluster

Gil Cohen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers

1 author row

FOCS Conference 2024 Conference Paper

Tight Bounds for the Zig-Zag Product

Gil Cohen
Itay Cohen 0003
Gal Maor

The Zig-Zag product of two graphs, $Z= G\bigcirc{\! \! \! \! \! \! \mathrm{z}}\ 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 the Zig-Zag product can be bounded roughly by the sum of the spectral expansions of the individual graphs, $\omega z\leq\omega_{H}+\omega_{G}$. In this work we derive, for every (vertex-transitive) c-regular graph $H$ on $d$ vertices, a tight bound for $\omega z$ by taking into account the entire spectrum of $H$. Our work reveals that the bound, which holds for every graph $G$, is precisely the minimum value of the function \begin{equation*}\frac{x}{c^2} \cdot \sqrt{1-\frac{d \cdot h(x)}{x \cdot h^{\prime}(x)}}\end{equation*} in the domain $(c^{2}, \ \infty)$, where $h(x)$ is the characteristic polynomial of $H^{2}$. As a consequence, we establish that Zig-Zag products are indeed intrinsically quadratic away from being Ramanujan. We further prove tight bounds for the spectral ex-pansion of the more fundamental replacement product. Our lower bounds are based on results from analytic combinatorics, and we make use of finite free probability to prove their tightness. In a broader context, our work uncovers intriguing links between the two fields and these well-studied graph operators.

Details

STOC Conference 2023 Conference Paper

Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Gil Cohen
Dean Doron
Ori Sberlo
Amnon Ta-Shma

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 BPL vs. L problem. The seminal work by Saks and Zhou [JCSS ’99] gives a deterministic algorithm for approximating the product of n stochastic matrices of dimension w × w in space O (log 3/2 n + √log n · log w ). The first improvement upon Saks–Zhou was achieved by Hoza [RANDOM ’21] who gave a logarithmic improvement in the n=poly(w) regime, attaining O (1/√loglog n · log 3/2 n ) space. We give the first polynomial improvement over Saks and Zhou’s algorithm. Our algorithm achieves space complexity of O (log n + √log n · log w ). In particular, in the regime log n > log 2 w , our algorithm runs in nearly-optimal O (log n ) space, improving upon the previous best O (log 3/2 n ). To obtain our result for the special case of matrix powering, we harness recent machinery from time- and space-bounded Laplacian solvers to the Saks–Zhou framework and devise an intricate precision-alternating recursive scheme. This enables us to bypass the bottleneck of paying log n -space per recursion level. The general case of iterated matrix multiplication poses several additional challenges, the substantial of which is handled by devising an improved shift and truncate mechanism. The new mechanism is made possible by a novel use of the Richardson iteration.

Details

STOC Conference 2023 Conference Paper

Random Walks on Rotating Expanders

Gil Cohen
Gal Maor

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 an example, when G is a d -regular Ramanujan graph, the power graph G t has spectral expansion 2 Ω( t ) √ D , where D = d t is the regularity of G t , thus, G t is 2 Ω( t ) away from being Ramanujan. This exponential blowup manifests itself in many applications.

Details

STOC Conference 2022 Conference Paper

Explicit binary tree codes with sub-logarithmic size alphabet

Inbar Ben Yaacov
Gil Cohen
Tal Yankovitz

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 the depth of the tree. Insisting on a constant number of colors at the expense of having vanishing distance, Gelles, Haeupler, Kol, Ron-Zewi, and Wigderson (SODA 2016) constructed a distance Ω(1/log n ) tree code. In this work we improve upon these prior works and construct a distance-δ tree code with (log n ) O (√δ) colors. This is the first construction of a constant distance tree code with sub-logarithmic number of colors. Moreover, as a direct corollary we obtain a tree code with a constant number of colors and distance Ω(1/(loglog n ) 2 ), exponentially improving upon the above-mentioned work by Gelles et al.

Details

FOCS Conference 2022 Conference Paper

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Gil Cohen
Tal Yankovitz

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 codeword. An RLDC, however, is allowed to abort when identifying corruption. The natural analog to locally correctable codes, dubbed relaxed locally correctable codes (RLCC), was introduced by Gur, Ramnarayan and Rothblum (ITCS 2018) who constructed asymptotically-good length-nRLCC and RLDC with $(\log n)^{O(\log\log n)}$ queries. In this work we construct asymptotically-good RLDC and RLCC with an improved query complexity of $(\log n)^{O(\log\log\log n)}$. To achieve this, we devise a mechanism-an alternative to the tensor product-that squares the length of a given code. Compared to the tensor product that was used by Gur et al. and by many other constructions, our mechanism is significantly more efficient in terms of rate deterioration, allowing us to obtain our improved construction.

Details

STOC Conference 2021 Conference Paper

Expander random walks: a Fourier-analytic approach

Gil Cohen
Noam Peri
Amnon Ta-Shma

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 → {0,1} cannot distinguish t independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and Szemeredi (STOC 1987) is captured by the AND test function, whereas the fundamental expander Chernoff bound due to Gillman (SICOMP 1998), Heally (Computational Complexity 2008) is about test functions indicating whether the weight is close to the mean. In fact, it is known that all threshold functions are fooled by a random walk (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Recently, it was shown that even the highly sensitive PARITY function is fooled by a random walk Ta-Shma (STOC 2017).

Details

STOC Conference 2018 Conference Paper

Explicit binary tree codes with polylogarithmic size alphabet

Gil Cohen
Bernhard Haeupler
Leonard J. Schulman

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant distance and alphabet size poly (log n ), where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size poly ( n ). At the core of our construction is the first explicit tree code with constant rate and constant distance, though with non-constant arity - a result of independent interest. This construction adapts the polynomial interpolation framework to the online setting.

Details

STOC Conference 2018 Conference Paper

Hitting sets with near-optimal error for read-once branching programs

Mark Braverman
Gil Cohen
Sumegha Garg

Nisan (Combinatorica’92) constructed a pseudorandom generator for length n , width n read-once branching programs (ROBPs) with error ε and seed length O (log 2 n + log n · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O (log n +log(1/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL , respectively. In contrast to a successful line of work in restricted settings, no progress has been made for general, unrestricted, ROBPs. Indeed, Nisan’s construction is the best pseudorandom generator and, prior to this work, also the best hitting set for unrestricted ROBPs. In this work, we make the first improvement for the general case by constructing a hitting set with seed length O (log 2 n +log(1/ε)). That is, we decouple ε and n , and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, log(1/ε) ≫ log n , is well-motivated by the work of Saks and Zhou (J.CSS’99) who use pseudorandom generators with error ε = 2 −(log n ) 2 in their proof for BPL ⊆ L 3/2 . We further suggest a research program towards proving that BPL ⊆ L 4/3 in which our result achieves one step. As our main technical tool, we introduce and construct a new type of primitive we call pseudorandom pseudo-distributions. Informally, this is a generalization of pseudorandom generators in which one may assign negative and unbounded weights to paths as opposed to working with probability distributions. We show that such a primitive yields hitting sets and, for derandomization purposes, can be used to derandomize two-sided error algorithms.

Details

STOC Conference 2017 Conference Paper

Towards optimal two-source extractors and Ramsey graphs

Gil Cohen

The main contribution of this work is a construction of a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent n -bit sources with min-entropy Ο(log n ), which is optimal up to the poly (loglog n ) factor. A strong motivation for constructing two-source extractors for low entropy is for Ramsey graphs constructions. Our two-source extractor readily yields a (log n ) (logloglog n ) Ο(1) -Ramsey graph on n vertices. Although there has been exciting progress towards constructing O (log n )-Ramsey graphs in recent years, a line of work that this paper contributes to, it is not clear if current techniques can be pushed so as to match this bound. Interestingly, however, as an artifact of current techniques, one obtains strongly explicit Ramsey graphs, namely, graphs on n vertices where the existence of an edge connecting any pair of vertices can be determined in time poly (log n ). On top of our strongly explicit construction, in this work, we consider algorithms that output the entire graph in poly ( n )-time, and make progress towards matching the desired Ο(log n ) bound in this setting. In our opinion, this is a natural setting in which Ramsey graphs constructions should be studied. The main technical novelty of this work lies in an improved construction of an independence-preserving merger (IPM), a variant of the well-studied notion of a merger, which was recently introduced by Cohen and Schulman. Our construction is based on a new connection to correlation breakers with advice. In fact, our IPM satisfies a stronger and more natural property than that required by the original definition, and we believe it may find further applications.

Details

FOCS Conference 2016 Conference Paper

Extractors for Near Logarithmic Min-Entropy

Gil Cohen
Leonard J. Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any δ > 0 we construct an extractor for O(1/δ) n-bit sources with min-entropy (logn) 1+δ. This is most interesting when δ is set to a small constant, though the result also yields an extractor for O(log logn) sources with logarithmic min-entropy. Prior to this work, the best explicit extractor in terms of supporting least-possible min-entropy, due to Li (FOCS'15), requires min-entropy (logn) 2+δ from its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors "break" below min-entropy (log n) 2. In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n) 1. 99. Apart from being a natural problem, supporting logarithmic min-entropy has applications to combinatorics. A two-source disperser, let alone an extractor, for min-entropy O(log n) induces a (log, nO(1))-Ramsey graph on n vertices. Thus, constructing such dispersers would be a significant step towards constructively matching Erdös' proof for the existence of (2log n)-Ramsey graphs on n vertices. Our construction does not rely on the sophisticated primitives that were key to the substantial recent progress on multi-source extractors, such as non-malleable extractors, correlation breakers, the lightest-bin condenser, or extractors for non-oblivious bit-fixing sources, although some of these primitives can be combined with our construction so to improve the output length and the error guarantee. Instead, at the heart of our construction is a new primitive called an independence-preserving merger. The construction of the latter builds on the alternating extraction technique.

Details

FOCS Conference 2016 Conference Paper

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

Gil Cohen

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 nonmalleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These are algorithms that break the correlation a “bad” random variable Y ' has with a “good” random variable Y using an “advice” - a fixed string α that is associated with Y which is guaranteed to be distinct from the corresponding string α' associated with Y '. Prior to this work, explicit constructions of correlation breakers with advice require the entropy of the involved random variables to depend linearly on the advice length. In this work, building on independence-preserving mergers, a pseudorandom primitive that was recently introduced by Cohen and Schulman, we devise a new construction of correlation breakers with advice that has optimal, logarithmic, dependence on the advice length. This enables us to obtain the following results. . We construct an extractor for 5 independent n-bit sources with min-entropy (log n) 1+o(1). This result puts us tantalizingly close to the goal of constructing extractors for 2 sources with min-entropy O(log n), which would have exciting implications to Ramsey theory. . We construct non-malleable extractors with error guarantee ε for n-bit sources, with seed length d = O(log n)+ (log(1/ε)) 1+o(1) for any min-entropy k = Ω(d). Prior to this work, all constructions require either very high minentropy or otherwise have seed length ω(log n) for any ε. Further, our extractor has near-optimal output length. Prior constructions that achieve comparable output length work only for very high min-entropy k ≈ n/2. . By instantiating the Dodis-Wichs framework with our non-malleable extractor, we obtain near-optimal privacy amplification protocols against active adversaries, improving upon all (incomparable) known protocols.

Details

STOC Conference 2016 Conference Paper

Two-source dispersers for polylogarithmic entropy and improved ramsey graphs

Gil Cohen

In his influential 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of 2log n -Ramsey graphs on n vertices. Matching Erdős’ result with a constructive proof is considered a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in the celebrated paper by Barak, Rao, Shaltiel, and Wigderson who constructed a 2 2 (loglog n ) 1−α -Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2 (loglog n ) c -Ramsey graphs, for some universal constant c . In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two n -bit sources with entropy ( n ). In fact, our disperser is a zero-error disperser that outputs a constant fraction of the entropy. Prior to this work, such dispersers could only support entropy Ω( n ).

Details

FOCS Conference 2015 Conference Paper

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

Gil Cohen

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 with the following property. If the i'th input random variable is uniform then the i'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to break local correlations between random variables. Our construction of LCBs has applications to three-source extractors, mergers with weak-seeds, and a variant of non-malleable extractors, that we introduce.

Details

FOCS Conference 2014 Conference Paper

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

Itai Benjamini
Gil Cohen
Igor Shinkar

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 E N there exists an explicit bijection ψ: {0, 1} n → {x E {0, 1}n+1: |x| > n/2} such that for every x ≠ y E {0, 1} n+1 it holds that 1/5 ≤ dist(ψ(x), ψ(y)) ≤ 4 5 - dist(x, y) where dist(·, ·) denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive. This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC°, but not in AC°. Moreover, we prove that ψ is “approximately local” in the sense that all but the last output bit of ψ are essentially determined by a single input bit.

Details