Hi! My name is Gil Cohen. I am a faculty member at the School of Computer Science at Tel-Aviv University. I am part of the Theory of Computation Group.
Announcements
November 19 2019. In the current semester, I'm also giving a seminar on Riemann Surfaces and Algebraic Curves. See the seminar homepage.
August 6 2019. In the coming semester, I'll be giving a course called Topics in Coding Theory: Locality and Interaction (instead of the previously advertised followup course on Algebraic-Geometric Codes). The course is an advanced course. We will study fascinating problems at the forefront of coding theory research, whose solutions beautifully mix combinatorics, algebra, and probability. See the course homepage for further details.
My Research Interests
My interests lie mostly in theoretical computer science with a focus on pseudo-randomness, explicit constructions, and computational complexity, as well as coding theory. In general, I am fascinated by the role that randomness plays in computation and in mathematics. More specifically, some of the topics I'm interested in are:
Derandomizing space-bound computation. The BPL vs. L problem captures the computational power that randomness adds to space-bounded algorithms. See a paper with Mark Braverman and Sumegha Garg in which we make progress on this problem since the early '90s.
Tree codes. These are elegant combinatorial structures that were introduced by Schulman. The definition is so clean, I can give it here! A tree code is an edge-colored, rooted complete binary tree such that the colors on the paths to every two vertices with equal depth disagree on a constant fraction of the respective edges starting from their least common ancestor (survived so far?). Schulman proved that tree codes with a constant number - independent of depth - of colors exist! Up until recently though, the best explicit construction, from the '90s, required poly(depth) colors--a huge gap. In joint work with Bernhard Haeupler and Leonard Schulman, we improved that exponentially to polylog(depth). I gave a two-hour chalk talk at IAS on this work. Leonard gave an excellent talk at IIAS.
Algebraic-geometric codes. Polynomials have a myriad of applications in theoretical computer science. The analysis is typically based on (increasingly sophisticated applications of) the fundamental theorem of algebra. It is amazing how much was squeezed out of it. Now, imagine what could be accomplished using far deeper results from algebraic geometry such as the Riemann-Roch Theorem! Coding theory had certainly benefited from AG and I believe more applications are waiting to be discovered. If you want to learn more, see an introductory lecture to AG codes that I gave at IAS. The talk is aimed at curious theoretical computer scientists and assumes no AG background. See also the website of my introduction to AG codes course that I gave.
Randomness extractors and Ramsey graphs. Randomness extractors are algorithms that extract "pure" randomness from imperfect random sources. Constructing these algorithms was my main passion for the last couple of years, partly motivated by the classic problem of constructing Ramsey graphs. Eshan Chattopadhyay, Xin Li and I organized a workshop on the subject as part of the STOC 2018 Theory Fest. If you want to learn more, check out the workshop homepage. Also, if you are interested in Ramsey graphs, see my IAS video talk (Part 1 and Part 2).
I am also interested in coding theory - interactive and otherwise, lower bounds, quantum computation. I enjoy working on clean combinatorial problems and cryptography from time to time.