Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with encoding:
TR97-046 | 3rd October 1997
Alexander Barg

Complexity Issues in Coding Theory

This is a research-expository paper. It deals with
complexity issues in the theory of linear block codes. The main
emphasis is on the theoretical performance limits of the
best known codes. Therefore, the main subject of the paper are
families of asymptotically good codes, i.e., codes whose rate and
relative ... more >>>

TR12-058 | 5th May 2012
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

How to Garble Arithmetic Circuits

Revisions: 1

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$
into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each
input bit, such that $\hat{C}$ together with the $n$ keys
corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$.
The garbled circuit ... more >>>

TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

ISSN 1433-8092 | Imprint