enter search term and/or author name
On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna
Ketan D. Mulmuley
Article No.: 5
This article gives an overview of the geometric complexity theory (GCT) approach towards the P vs. NP and related problems focusing on its main complexity theoretic results. These are: (1) two concrete lower bounds, which are currently the best...
Delaunay triangulations in O(sort(n)) time and more
Kevin Buchin, Wolfgang Mulzer
Article No.: 6
We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where...
This article deals with the emulation of atomic read/write (R/W) storage in dynamic asynchronous message passing systems. In static settings, it is well known that atomic R/W storage can be implemented in a fault-tolerant manner even if the...
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
Haim Avron, Sivan Toledo
Article No.: 8
We analyze the convergence of randomized trace estimators. Starting at 1989, several algorithms have been proposed for estimating the trace of a matrix by 1/M∑i=1M ziT...