Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Elimination:
TR01-019 | 2nd March 2001
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

The Communication Complexity of Enumeration, Elimination, and Selection

Normally, communication Complexity deals with how many bits
Alice and Bob need to exchange to compute f(x,y)
(Alice has x, Bob has y). We look at what happens if
Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n
and they want to compute f(x_1,y_1)... f(x_n,y_n).
THis seems hard. We look at various ... more >>>

TR03-036 | 27th April 2003
Bruce Edward Litow

Polynomial equation elimination via Tarski Algebra

The elimination
problem is classical:
implicitly express one of the variables occurring in a finite
system of polynomial equations as an algebraic function of a
designated subset of the remaining variables. Solutions to this
problem by resultants, or more comprehensively by
use of Gr\"{o}bner basis methods are available. In this ... more >>>

ISSN 1433-8092 | Imprint