Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MIDDLE BIT:
Reports tagged with middle bit:
TR04-107 | 24th November 2004
Ingo Wegener, Philipp Woelfel

New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.
This paper contains several new results on its complexity.
First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.
A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>


TR21-031 | 3rd March 2021
Vaibhav Krishan

Upper Bound for Torus Polynomials

We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>




ISSN 1433-8092 | Imprint