Saugata Basu

FOCS Conference 2025 Conference Paper

Solving Linear Inequalities over the Space of Convex Sets & its Applications to Cryptography and Hydrodynamics

• Saugata Basu
• Hamidreza Amini Khorasgani
• Hemanta K. Maji
• Hai H. Nguyen

Is a two-party function, possibly with randomized output, securely computable? We provide a finite procedure to answer this question, thereby settling a foundational, three-decade-old open problem in secure computation and information complexity. Beaver-Chor-Kushilevitz [11], [22], [8] answered this question for deterministic output functions. Basu et al. [3] recently gave a geometric characterization of randomized functions securely computable with bounded communication complexity. Randomized functions can have arbitrarily high communication complexity, even for fixed input-output sets [5]. Without an upper bound on the communication complexity, the decidability of the question of whether a given two-party function with randomized output is securely computable was a formidable challenge. We reduce answering this question to proving specific lamination hulls are semi-algebraic. Lamination hulls are an infinite union of recursively defined sets independently motivated by the hydrodynamics literature. We connect this technical objective to solving a system of linear inequalities over convex sets in high dimensions, where inequalities represent the natural containment relation. We present a Gaussian elimination-inspired algorithm to compute the smallest simultaneous solutions to such systems. After that, using these solutions, we prove that our lamination hulls are semi-algebraic. Our technical solution introduces a novel set operator called positive geometric join. In our application context, it characterizes algebraically well-behaved sets that generalize polytopes, which we call hemihedra. The positive geometric join operator and hemihedral sets should interest the broader mathematics and computer science community. These advancements should help further information complexity investigations more broadly via the recently established connection by Basu et al. [3].

FOCS Conference 2022 Conference Paper

Geometry of Secure Two-party Computation

• Saugata Basu
• Hamidreza Amini Khorasgani
• Hemanta K. Maji
• Hai H. Nguyen

What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points. 1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints. 2)We construct one such protocol if it exists. 3)Otherwise, we present an obstruction to achieving security. Our technical contributions imply new information complexity bounds for secure computation.

FOCS Conference 2021 Conference Paper

Harmonic Persistent Homology (extended abstract)

• Saugata Basu
• Nathanael Cox

We introduce harmonic persistent homology spaces for filtrations of finite simplicial complexes. As a result we can associate concrete subspaces of cycles to each bar of the barcode of the filtration. We prove stability of the harmonic persistent homology subspaces under small perturbations of functions defining them. We relate the notion of “essential simplices, ” introduced in an earlier work to identify simplices which play a significant role in the birth of a bar, with that of harmonic persistent homology. We prove that the harmonic representatives of simple bars maximizes the “relative essential content” amongst all representatives of the bar, where the relative essential content is the weight a particular cycle puts on the set of essential simplices.

FOCS Conference 2009 Conference Paper

Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem

• Saugata Basu
• Thierry Zell

Toda proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P #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 #P. This result which illustrates the power of counting is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of BlumShub-Smale real Turing machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry.

STOC Conference 2007 Conference Paper

Combinatorial complexity in O-minimal geometry

• Saugata Basu

STOC Conference 2005 Conference Paper

Computing the first Betti number and the connected components of semi-algebraic sets

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

STOC Conference 2005 Conference Paper

Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities

• Saugata Basu

For any fixed l > 0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P 1 ≥ 0,...,P s ≥ 0, where each P i ∈ R[X 1 ,...,X k ] has degree ≤ 2, and computes the top l Betti numbers of S, b k-1 (S), ..., b k-l (S), in polynomial time. The complexity of the algorithm, stated more precisely, is Σ i=0 l+2 ( s i k 2 O((l,s)) . For fixed l, the complexity of the algorithm can be expressed as s l+2 k 2 O(l) , which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in R k defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed s, we obtain by letting l = k, an algorithm for computing all the Betti numbers of S whose complexity is k 2 O(s)

STOC Conference 2002 Conference Paper

Computing the betti numbers of arrangements

• Saugata Basu

(MATH) In this paper, we consider the problem of computing the Betti numbers of an arrangement of $n$ compact semi-algebraic sets, $S_1,\ldots,S_n \subset \R^k$, where each $S_i$ is described using a constant number of polynomials with degrees bounded by a constant. Such arrangements are ubiquitous in computational geometry. We give an algorithm for computing $\ell$-th Betti number, $\beta_\ell(\cup_i S_i), 0 \leq \ell \leq k-1$, using $O(n^{\ell+2})$ algebraic operations. Additionally, one has to perform linear algebra on matrices of size bounded by $O(n^{\ell+1})$. All previous algorithms for computing the Betti numbers of arrangements, triangulated the arrangement giving rise to a complex of size $O(n^{2^k})$ in the worst case. To our knowledge this is the first algorithm for computing $\beta_\ell(\cup_i S_i)$ that does not rely on such a global triangulation, and has a graded complexity which depends on $\ell$.

FOCS Conference 1998 Conference Paper

On the Combinatorial and Topological Complexity of a Single Cell

• Saugata Basu

The problem of bounding the combinatorial complexity of a single connected component (a single cell) of the complement of a set of a geometric objects in R/sup k/, each object of constant description complexity, is an important problem in computational geometry which has attracted much attention over the past decade. It has been conjectured that the combinatorial complexity of a single cell is bounded by a function much closer to O(n/sup k-1/) rather than O(n/sup k/) which is the bound for the combinatorial complexity of the whole arrangement. Till now, this was known to be rule only for k/spl les/3 and only for some special cases in higher dimensions. A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. However, till now no better bounds were known if we restricted attention to a single connected component of a basic semi-algebraic set. In this paper, we show how these two problems are related. We prove a new bound on the sum of the Betti numbers of one connected component of a basic semi-algebraic set which is an improvement over the Oleinik-Petrovsky-Thom-Milnor bound. This also implies that the topological complexity of a single cell, measured by the sum of the Betti numbers, is bounded by O(n/sup k-1/).

FOCS Conference 1997 Conference Paper

An Improved Algorithm for Quantifier Elimination Over Real Closed Fields

• Saugata Basu

We give a new algorithm for quantifier elimination in the first order theory of real closed fields that improves the complexity of the best known algorithm for this problem till now. Unlike previously known algorithms the combinatorial part of the complexity of this new algorithm is independent of the number of free variables. Moreover, under the assumption that each polynomial in the input depend only on a constant number of the free variables, the algebraic part of the complexity can also be made independent of the number of free variables. This new feature of our algorithm allows us to obtain a new algorithm for a variant of the quantifier elimination problem. We give an almost optimal algorithm for this new problem, which we call the uniform quantifier elimination problem and apply it to solve a problem arising in the field of constraint databases. No algorithm with reasonable complexity bound was known for this latter problem till now. We also point out interesting logical consequences of this algorithmic result, concerning the expressive power of a constraint query language over the reals. Moreover, our improved algorithm for performing quantifier elimination immediately leads to improved algorithms for several problems for which quantifier elimination is a basic step, for example, the problem of computing the closure of a given semi-algebraic set.

STOC Conference 1996 Conference Paper

Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract)

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

STOC Conference 1996 Conference Paper

On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

• Saugata Basu

FOCS Conference 1994 Conference Paper

On the Combinatorial and Algebraic Complexity of Quantifier Elimination

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

In this paper we give a new algorithm for performing quantifier elimination from first order formulae over real closed fields. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this date. A new feature of our algorithm is that the role of the algebraic part (the dependence on the degrees of the input polynomials) and the combinatorial part (the dependence on the number of polynomials) are separated, making possible our improved complexity bound. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that we output, are independent of the number of input polynomials. As special cases of this algorithm, we obtain new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields. Using the theory developed in this paper, we also give an improved bound on the radius of a ball centered at the origin, which is guaranteed to intersect every connected component of the sign partition induced by a family of polynomials. We also use our methods to obtain algorithms for solving certain decision problems in real and complex geometry which improves the complexity of the currently known algorithms for these problems. >