Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR25-037 | 31st March 2025
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

Uniform Bounds on Product Sylvester-Gallai Configurations

Revisions: 1

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is ... more >>>


TR25-036 | 29th March 2025
Siddharth Iyer

Lifting for Arbitrary Gadgets

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f: \{0,1\}^n\to \{0,1\}$ and $g : \mathcal{X} \times \mathcal{Y}\to \{0,1\}$, denote $f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$,
\[D(f\circ g) \geq s\cdot \bigg(\frac{\Omega(D(g))}{\log rk(g)} - \log rk(g)\bigg),\]
where ... more >>>


TR25-035 | 25th March 2025
Abhibhav Garg, Rafael Mendes de Oliveira, Nitin Saxena

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals

A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, ... more >>>



Next next


ISSN 1433-8092 | Imprint