Fwd: Distributing a message re TCS student seminar

[Arnold Filtser]

Hello to all students,

There is a weakly student theory seminar, happening in TAU, on Sundays.

See details below.

Best,

Arnold

Hi All!

Starting December 7, we will have a special seminar for TCS students from multiple institutes, and we would love to have you there!
One of our goals is for theory students to get to know each other and provide a conducive atmosphere to discuss our research (or anything else).

On Sunday, December 7, we will have our first talk by Nathan Wallheimer (Weizmann Institute), who will tell us about fine-grained complexity and his recent results about triangle detection in H-free graphs.

The talk will be given at Check Point 280, Tel Aviv University.

Abstract is attached below.

Some technicalities:
- Who is the seminar for? Graduate students researching TCS (including algorithms, crypto, etc.)

- Where is it going to be held? In room 280 at CheckPoint building, Tel-Aviv university.

- When? Sundays, 10:10-12:00 (including a short break). We will meet every two weeks (excluding holidays and conferences), starting from December 7 until the end of June.
You can add the seminar calendar to your Google account using the following link.

- What to expect? Talks by students like you and us spanning different areas of TCS.
It's a good opportunity to share your recent results, shape your presentations, or discuss any exciting results or techniques you think others should know about.
(Would you like to give a talk at the seminar? Please email us!)

- I wish to know more! What should I do? Join our mailing list by following this simple procedure:
a. Email an empty message to theory_student_s...@googlegroups.com.
b. You will get an email back. Reply to it with yet another empty email (which seems more reliable than pressing the suggested "Join This Group" button).
c. You should receive a confirmation message within 24 hours - congrats! If you haven't gotten it - please write to us for a quick fix.

You are more than welcome to share the seminar with any students that might be interested, sign up to give a talk, write to us about anything, and, most of all - join us! We would love to see you there!

Title: Triangle detection in H-free graphs.

Amir Abboud, Ron Safier, Nathan Wallheimer.

Abstract:

We initiate the study of combinatorial algorithms for Triangle Detection in H-free graphs. The goal is to decide if a graph that forbids a fixed pattern H as a subgraph contains a triangle, using only “combinatorial” methods that notably exclude fast matrix multiplication. Our work aims to classify which patterns admit a subcubic speedup, working towards a dichotomy theorem. On the lower bound side, we show that if H is not 3-colorable or contains more than one triangle, the complexity of the problem remains unchanged, and no combinatorial speedup is likely possible. On the upper bound side, we develop an embedding approach that results in a strongly subcubic, combinatorial algorithm for a rich class of “embeddable” patterns. Specifically, for an embeddable pattern of size k, our algorithm runs in $\tilde{O}(n^{3− 1/2^{k−3}})$ time, where $\tilde{O}$ hides polylogarithmic factors. This algorithm also extends to listing all the triangles within the same time bound. We supplement this main result with two generalizations: 

• A generalization to patterns that are embeddable up to a single obstacle that arises from a triangle in the pattern. This completes our classification for small patterns, yielding a dichotomy theorem for all patterns of size up to eight. 

• An H-sensitive algorithm for embeddable patterns, which runs faster when the number of copies of H is significantly smaller than the maximum possible Ω(n^k). Finally, we focus on the special case of odd cycles. We present specialized Triangle Detection algorithms that are very efficient: 

• A combinatorial algorithm for C_{2k+1}-free graphs that runs in \tilde{O}(m+n^{1+2/k}) time for every k ≥ 2, where m is the number of edges in the graph. 

• A combinatorial C_5-sensitive algorithm that runs in \tilde{O}(n^2 + n^{4/3} t^{1/3}) time, where t is the number of 5-cycles in the graph.

 

See you soon,

Shay Sapir

shay1...@gmail.com