Accueil

Saugata Basu

  1. Toric cubes are closed balls.

    Tue, 02/28/2012 - 15:01 — SomNambul
    Authors: Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
    Subjects: Algebraic Geometry
    Abstract

    We prove that toric cubes, which are images of $[0,1]^d$ under monomial maps,
    are the closures of graphs of monotone maps, and in particular
    semi-algebraically homeomorphic to closed balls.

  2. A baby step-giant step roadmap algorithm for general algebraic sets.

    Wed, 02/01/2012 - 15:01 — SomNambul
    Authors: Mohab Safey El Din, Saugata Basu, Marie-Françoise Roy, Éric Schost
    Subjects: Algebraic Geometry
    Abstract

    Let $\R$ be a real closed field and $\D \subset \R$ an ordered domain. We
    give an algorithm that takes as input a polynomial $Q \subset \D[X_1,...,X_k]$,
    and computes a description of a roadmap of the set of zeros, $\ZZ(Q,\R^k)$, of
    $Q$ in $\R^k$. The complexity of the algorithm, measured by the number of
    arithmetic operations in the domain $\D$, is bounded by $d^{O(k \sqrt{k})}$,
    where $d = deg(Q)\ge 2$.

  3. A complex analogue of Toda's Theorem.

    Tue, 12/15/2009 - 16:01 — SomNambul
    Authors: Saugata Basu
    Subjects: Algebraic Geometry
    Abstract

    Toda proved in 1989 that the (discrete) polynomial time hierarchy,
    $\mathbf{PH}$, is contained in the class $\mathbf{P}^{#\mathbf{P}}$, namely the
    class of languages that can be decided by a Turing machine in polynomial time
    given access to an oracle with the power to compute a function in the counting
    complexity class $#\mathbf{P}$. This result which illustrates the power of
    counting is considered to be a seminal result in computational complexity
    theory.

  4. Bounding the radii of balls meeting every connected component of semi-algebraic sets.

    Mon, 11/09/2009 - 16:01 — SomNambul
    Authors: Saugata Basu, Marie-Francoise Roy
    Subjects: Symbolic Computation
    Abstract

    We prove explicit bounds on the radius of a ball centered at the origin which
    is guaranteed to contain all bounded connected components of a semi-algebraic
    set $S \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving
    $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$, and
    whose coefficients have bitsizes at most $\tau$. Our bound is an explicit
    function of $s, d, k$ and $\tau$, and does not contain any undetermined
    constants.

Math-arch

Syndicate content