Loading jsMath...
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