Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-180 | 15th December 2022
Aniruddha Biswas, Palash Sarkar

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture

Revisions: 1

We describe a new construction of Boolean functions. A specific instance of our construction provides a 30-variable Boolean function having min-entropy/influence ratio to be 128/45 ? 2.8444 which is presently the highest known value of this ratio that is achieved by any Boolean function. Correspondingly, 128/45 is also presently the ... more >>>


TR22-179 | 16th December 2022
Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Round-vs-Resilience Tradeoffs for Binary Feedback Channels

Revisions: 1

In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... more >>>


TR22-178 | 8th December 2022
Ilias Diakonikolas, Christos Tzamos, Daniel Kane

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

The Forster transform is a method of regularizing a dataset
by placing it in {\em radial isotropic position}
while maintaining some of its essential properties.
Forster transforms have played a key role in a diverse range of settings
spanning computer science and functional analysis. Prior work had given
{\em ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint