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-101 | 18th July 2025
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis

A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to ... more >>>


TR25-100 | 15th July 2025
Mika Göös, Nathaniel Harms, Artur Riazanov

Equality is Far Weaker Than Constant-Cost Communication

We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of ... more >>>


TR25-099 | 17th July 2025
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

The Algebraic Cost of a Boolean Sum

It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression.
We study the question of why the VNP-completeness proof of the permanent fails for the determinant.
We ... more >>>



Next next


ISSN 1433-8092 | Imprint