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

TR23-187 | 27th November 2023
Klim Efremenko, Michal Garlik, Dmitry Itsykson

Lower bounds for regular resolution over parities

Revisions: 2

The proof system resolution over parities (Res($\oplus$)) operates with disjunctions of linear equations (linear clauses) over $\mathbb{F}_2$; it extends the resolution proof system by incorporating linear algebra over $\mathbb{F}_2$. Over the years, several exponential lower bounds on the size of tree-like Res($\oplus$) refutations have been established. However, proving a superpolynomial ... more >>>


TR23-186 | 28th November 2023
Ce Jin, Ryan Williams, Nathaniel Young

A VLSI Circuit Model Accounting For Wire Delay

Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a ... more >>>


TR23-185 | 27th November 2023
Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

Revisions: 3

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint