Search Results

Documents authored by Even, Tomer

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.52
Witness-Sensitive Detection of Induced Diamonds

Authors: Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams, and Nathan Wallheimer

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We provide a fast witness-sensitive algorithm for detecting an induced diamond (a K₄ minus an edge) in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^2.425/t^0.25 + n², n^ω)) with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time O(n^ω log n) [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever t ≥ n^{(3-ω)/3}, where ω < 2.372 is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is r-heavy if this size is at least r, and we provide a fast detection algorithm for r-heavy diamonds in Õ(r⋅(n/r)^ω + (n/r)³+ nr) time. When there are no r-heavy diamonds, we provide a different fast detection algorithm in Õ(MM(n,n,n√{r/t})) time, where MM(a,b,c) denotes the time to multiply an a × b matrix by a b × c matrix, which is conditionally optimal for r = Õ(1). Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no r-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for 4-SUM and for a special case of 4-cycles.
Cite as

Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams, and Nathan Wallheimer. Witness-Sensitive Detection of Induced Diamonds. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2026.52,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia and Wallheimer, Nathan},
  title =	{{Witness-Sensitive Detection of Induced Diamonds}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{52:1--52:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.52},
  URN =		{urn:nbn:de:0030-drops-264419},
  doi =		{10.4230/LIPIcs.ICALP.2026.52},
  annote =	{Keywords: Induced diamond detection, Witness-sensitive algorithms, Matrix multiplication, Subgraph detection, Fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.12
Faster Cycle Detection in the Congested Clique

Authors: Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We provide a fast distributed algorithm for detecting h-cycles in the Congested Clique model, whose running time decreases as the number of h-cycles in the graph increases. In undirected graphs, constant-round algorithms are known for cycles of even length. Our algorithm greatly improves upon the state of the art for odd values of h. Moreover, our running time applies also to directed graphs, in which case the improvement is for all values of h. Further, our techniques allow us to obtain a triangle detection algorithm in the quantum variant of this model, which is faster than prior work. A key technical contribution we develop to obtain our fast cycle detection algorithm is a new algorithm for computing the product of many pairs of small matrices in parallel, which may be of independent interest.
Cite as

Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Faster Cycle Detection in the Congested Clique. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2024.12,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia},
  title =	{{Faster Cycle Detection in the Congested Clique}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.12},
  URN =		{urn:nbn:de:0030-drops-212382},
  doi =		{10.4230/LIPIcs.DISC.2024.12},
  annote =	{Keywords: triangle detection, cycle detection, distributed computing, Congested Clique, quantum computing, Fast matrix multiplication, Fast rectangular matrix multiplication}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.37
Fast Approximate Counting of Cycles

Authors: Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal.
Cite as

Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia},
  title =	{{Fast Approximate Counting of Cycles}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.37},
  URN =		{urn:nbn:de:0030-drops-201809},
  doi =		{10.4230/LIPIcs.ICALP.2024.37},
  annote =	{Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact