Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Parallel algorithms:
TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
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 >>>

TR07-028 | 12th February 2007
Daniel Sawitzki

Implicit Simulation of FNC Algorithms

Implicit algorithms work on their input's characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms ... more >>>

TR13-042 | 25th March 2013
Siu Man Chan

Just a Pebble Game

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>

TR16-050 | 31st March 2016
Roei Tell

Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

Revisions: 1

We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about $S$ is estimates of the density of $S$ in adaptively chosen subsets of ... more >>>

TR16-142 | 11th September 2016
Jason Li, Ryan O'Donnell

Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

TR20-074 | 6th May 2020
Eric Allender, Archit Chauhan, Samir Datta

Depth-First Search in Directed Graphs, Revisited

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>>

ISSN 1433-8092 | Imprint