Emanuele Viola

activity

20092026

most cited3SUM, 3XOR, Triangles

8 citations · 22 across the 12 of their papers we have counts for

collaborators

Showing 2013Show all

3 papers · 1 filter

cs.CC2013★ 1 cited

Challenges in computational lower bounds

Emanuele Viola

We draw two incomplete, biased maps of challenges in computational complexity lower bounds.

cs.CC2013

Local reductions

Hamid Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \geq 2^{n}$ to a 3SAT instance $ϕ$ of quasilinear size $∣ ϕ ∣ = T \cdot lo g^{O (1)} T$ such that there is an explicit circuit $C$ that on input an in…

cs.CC2013★ 8 cited

3SUM, 3XOR, Triangles

Zahra Jafargholi, Emanuele Viola

We show that if one can solve 3SUM on a set of size n in time n^{1+\e} then one can list t triangles in a graph with m edges in time O(m^{1+\e}t^{1/3-\e/3}). This is a reversal of…