Volume 28; Issue 3

SIAM Journal on Computing

Volume 28; Issue 3
1

Solvability of Consensus: Composition Breaks Down for NonDeterministic Types

Jayanti, Prasad
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 367 KB
english, 1998
3

A Lower Bound for Integer Multiplication with Read-Once Branching Programs

Ponzio, Stephen
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 458 KB
english, 1998
4

Fast Connected Components Algorithms for the EREW PRAM

Karger, David R., Nisan, Noam, Parnas, Michal
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 355 KB
english, 1998
5

Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors

Hind, Hugh, Molloy, Michael, Reed, Bruce
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 266 KB
english, 1998
6

Products and Help Bits in Decision Trees

Nisan, Noam, Rudich, Steven, Saks, Michael
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 380 KB
english, 1998
7

Computing components and projections of curves over finite fields

von zur Gathen, Joachim, Shparlinski, Igor
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 429 KB
english, 1998
9

Bipartite Edge Coloring in $O(\Delta m)$ Time

Schrijver, Alexander
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 253 KB
english, 1998
11

Row-Major Sorting on Meshes

Sibeyn, Jop F.
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 399 KB
english, 1998
13

The Maximum Partition Matching Problem with Applications

Chen, Chi-Chang, Chen, Jianer
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 410 KB
english, 1998
14

Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions

Kao, Ming-Yang, Qi, Junfeng, Tan, Lei
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 329 KB
english, 1998
15

Three-Processor Tasks Are Undecidable

Gafni, Eli, Koutsoupias, Elias
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 273 KB
english, 1998
17

Simple Algorithms for Routing on Butterfly Networks with Bounded Queues

Maggs, Bruce M., Sitaraman, Ramesh K.
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 378 KB
english, 1998
18

Efficient Database Updates with Independent Schemes

Torlone, Riccardo, Atzeni, Paolo
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 467 KB
english, 1998
19

Failure Detection and Randomization: A Hybrid Approach to Solve Consensus

Aguilera, Marcos Kawazoe, Toueg, Sam
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 318 KB
english, 1998
20

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

Bshouty, Nader H., Jackson, Jeffrey C.
Journal:
SIAM Journal on Computing
Year:
1998
Language:
english
File:
PDF, 384 KB
english, 1998