Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YAKOV NEKRICH:
All reports by Author Yakov Nekrich:

TR04-118 | 21st December 2004
Marek Karpinski, Yakov Nekrich

A Note on Traversing Skew Merkle Trees

We consider the problem of traversing skew (unbalanced) Merkle
trees and design an algorithm for traversing a skew Merkle tree
in time O(log n/log t) and space O(log n (t/log t)), for any choice
of parameter t\geq 2.
This algorithm can be of special interest in situations when
more >>>


TR04-049 | 15th June 2004
Piotr Berman, Marek Karpinski, Yakov Nekrich

Optimal Trade-Off for Merkle Tree Traversal

We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

more >>>

TR02-029 | 3rd June 2002
Marek Karpinski, Yakov Nekrich

Parallel Construction of Minimum Redundancy Length-Limited Codes

This paper presents new results on parallel constructions of the
length-limited prefix-free codes with the minimum redundancy.
We describe an algorithm for the construction of length-limited codes
that works in $O(L)$ time with $n$ processors for $L$ the
maximal codeword length.
We also describe an algorithm for a construction ... more >>>


TR02-018 | 22nd March 2002
Piotr Berman, Marek Karpinski, Yakov Nekrich

Approximating Huffman Codes in Parallel

In this paper we present some new results on the approximate parallel
construction of Huffman codes. Our algorithm achieves linear work
and logarithmic time, provided that the initial set of elements
is sorted. This is the first parallel algorithm for that problem
with the optimal time and ... more >>>




ISSN 1433-8092 | Imprint