Zobrazeno 1 - 10
of 121
pro vyhledávání: '"Abboud, Amir"'
Autor:
Abboud, Amir, Wallheimer, Nathan
A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving that the complexity remains unchanged if the input is assumed to be a
Externí odkaz:
http://arxiv.org/abs/2403.08394
Detecting if a graph contains a $k$-Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time $O(n^{\omega k/3})$, where $\omega$ is the exponent of Boolean matrix multiplication. To date, t
Externí odkaz:
http://arxiv.org/abs/2401.13502
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$;
Externí odkaz:
http://arxiv.org/abs/2311.09095
What is the time complexity of matrix multiplication of sparse integer matrices with $m_{in}$ nonzeros in the input and $m_{out}$ nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of $m_{in}$ vs
Externí odkaz:
http://arxiv.org/abs/2309.06317
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation
Externí odkaz:
http://arxiv.org/abs/2307.07583
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set $X \subseteq \Sigma^d$ of $n$ strings, find the string $x^*$ minimizing the radius of the smallest Hamming ba
Externí odkaz:
http://arxiv.org/abs/2305.16878
The Voronoi diagrams technique was introduced by Cabello to compute the diameter of planar graphs in subquadratic time. We present novel applications of this technique in static, fault-tolerant, and partially-dynamic undirected unweighted planar grap
Externí odkaz:
http://arxiv.org/abs/2305.02946
Autor:
Abboud, Amir, Wallheimer, Nathan
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful hammer has led the community to (1) believe that most problems are as eas
Externí odkaz:
http://arxiv.org/abs/2211.12833
In this note we present an algorithm that lists all $4$-cycles in a graph in time $\tilde{O}(\min(n^2,m^{4/3})+t)$ where $t$ is their number. Notably, this separates $4$-cycle listing from triangle-listing, since the latter has a $(\min(n^3,m^{3/2})+
Externí odkaz:
http://arxiv.org/abs/2211.10022
The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an $n^{1/2}$-regular graph is $n
Externí odkaz:
http://arxiv.org/abs/2211.07058