Browse Reports

The binary hypercube has many properties that make it attractive as an interconnection network for parallel computation: expansibility, symmetry, and a diameter that is logarithmic to the number of processors. However, the hypercube is not the minimum-...

An argument to reject the ''universal acceptance of logic'' thesis and its implications.

A closed-form expression is derived for the memory bandwidth obtained when N processors are permitted to generate requests to M memory modules. Use of generating functions is made, in a rather unusual fashion, to obtain this expressio n. The one ...

We consider the problem of sampling ``unlabelled structures'''', i.e., sampling combinatorial structures modulo a group of symmetries. The main tool which has been used for this sampling problem is Burnside''s lemma. In situations where a significant ...

ARRAY(0x845272c) OF CONCRETE LINGUISTIC RESOURCES. I HAVE IDENTIFIED THREE KINDS OF INFORMA

The retrieval effectiveness of large document collections is normally assessed by using small subsections of the file for test purposes, and extrapolating the data upward to represent the results for the full collection. The accuracy of such an ...

We construct a polynomial time $(\e,\d)$-approximation algorithm for estimating the number of zeros of an arbitrary multilinear polynomial $f(\xes)$ over \gf{q}. This extends the recent result of Karpinski/Luby (\cite{KL90a}) on approximating the number ...

For the ${GI/G/1}$ queueing model with heavy-tailed service- and arrival time distributions and traffic $a0 \}$, when properly scaled, i.e. ${\Delta (a)} {\rm v}_{\tau / {\Delta_1 (a)}}$ for ${a \uparrow 1 }$ with ${\Delta_1 (a)} = {\Delta (a)} (1-a)$. ...

Given a univariate complex polynomial $f(x)$ of degree $n$ with rational coefficients expressed as a ratio of two integers $> 2^m$, the {\em root problem} is to find all the roots of $f(x)$ up to specified precision $2^{-\mu}$. In this paper we assume ...

A simple algorithm is described which determines the satisfiability over the reals of a conjunction of linear inequalities, none of which contains more than two variables. In the worst case the algorithm requires time O(${mn}^{\lceil \log^2 n \rceil + 3}...

The kernel of a polygon {\bf P} is the set of all points that see the interior of {\bf P}. It can be computed as the intersection of the halfplanes that are to the left of the edges of {\bf P}. We present an $O(\log\log n)$ time CRCW-PRAM algorithm ...

The probability of a property on the collection of all finite relational structures is the limit as n --< infinity of the fraction of structures with n elements satisfying the property, provided the limit exists. It is known that the 0-1 law holds for ...

We investigate asymptotic probabilities of properties expressible in the infinitary logic L^omega_{infinity omega} on finite structures. Sentences in this logic may have arbitrary disjunctions and conjunctions, but they involve only a finite number of ...

Concurrent systems are often modeled by labeled state--transition graphs called Kripke Structures~\cite{browne_clarke_grumberg_2}. To reason about such systems, one standard approach is to provide a temporal semantic for the structure. Properties of ...