Hi! My name is Gil Cohen. I am a faculty member at the Department of Computer Science at Tel-Aviv University. I am part of the Theory of Computation Group.
Announcements
July 11 2020. In the coming semester I will give a course on spectral graph theory. If you have no idea what that is, I recommend Spielman's Miracles of Algebraic Graph Theory talk that gives a highly insightful introduction to the field. We will mostly follow Spielman's book-in-progress, though the course will have a stronger emphasis on theoretical computer science (as opposed to combinatorial) applications. See more details on the course homepage.
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.