Seminar Upcoming

The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.

Wednesdays, 13:00-14:00 (food starts at 12:45)
Room 201 (note return to traditional room), Taub Building

If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.

The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.

To join or leave our mailing list.

Output-sensitive approximate counting via a measure-bounded hyperedge oracle. or: How asymmetry helps estimate k-clique counts faster

Show and Hide Ext. Content for Output-sensitive approximate counting via a measure-bounded hyperedge oracle. or: How asymmetry helps estimate k-clique counts faster

Wed, June 11

Tomer Even (Technion)

Detecting a k-clique in a graph, for k at least 3, is a fundamental problem in fine-grained complexity, conjectured to require n^(omega * k / 3 – o(1)) time, where omega is the matrix multiplication exponent. In this talk, we present new detection and approximate counting algorithms for graphs containing many k-cliques.

The talk is based on a joint work with Keren Censor-Hillel and Virginia Vassilevska Williams. To appear in STOC 2025.

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

Wed, June 18

Amit Levi (University of Haifa)

The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23]
concerns properties of distributions supported on $\{0,1\}^n$, where $n$ is so
large that even reading a single sampled string is unrealistic. Instead, query
access is provided to the samples, and the efficiency of the algorithm is
measured by the total number of queries that were made to them.

Index-invariant properties under this model were defined in [Chakraborty et
al., COLT 23], as a compromise between enduring the full intricacies of string
testing when considering unconstrained properties, and giving up completely on
the string structure when considering label-invariant properties.
Index-invariant properties are those that are invariant through a consistent
reordering of the bits of the involved strings.

Here we provide an adaptation of Szemer\’edi’s regularity method for this
setting, and in particular show that if an index-invariant property admits an
$\epsilon$-test with a number of queries depending only on the proximity
parameter $\epsilon$, then it also admits a distance estimation algorithm whose
number of queries depends only on the approximation parameter.

Itai Boneh (Reichman University and University of Haifa)

Wed, July 2

Itai Boneh (Reichman University and University of Haifa)

Ilan Komargodski (Hebrew University)

Wed, July 9

Ilan Komargodski (Hebrew University)

past seminar