O složitosti
On approximating NP-hard optimization problems.
On Bröcker's t-invariant and separating families for constructible sets.
On changes of input/output coding. I.
On changes of input/output coding. II.
On computations with integer division
On context constrained squares and repetitions in a string
On Convex Body Chasing.
On distributive fixed-point expressions
On Distributive Fixed-Point Expressions
For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size . Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
On extremum-searching approximate probabilistic algorithms
On hardly linearly provable systems
A well-known theorem of Rabin yields a dimensional lower bound on the width of complete polynomial proofs of a system of linear algebraic inequalities. In this note we investigate a practically motivated class of systems where the same lower bound can be obtained on the width of almost all (noncomplete) linear proofs. The proof of our result is based on the Helly Theorem.
On k-Sets in Arrangements of Curves and Surfaces.
On Levels in Arrangements and Voronoi Diagrams.
On locating a single path-like facility in a general graph
On nonlinear complexity of monotone realization of a family of Boolean sums.
On Nonnegative Solutions of Random Systems of Linear Inequalities.
On one NP-complete problem
On optimal methods in numerical analysis
Round-off error analysis of the gradient method.
On parameters of an evaluation function for heuristic search as a path problem