Source author record

Bharat Adsul

Bharat Adsul appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

11works
9topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Geometric Complexity Theory -- Lie Algebraic Methods for Projective Limits of Stable Points

Let $G$ be a connected reductive group acting on a complex vector space $V$ and projective space ${\mathbb P}V$. Let $x\in V$ and ${\cal H}\subseteq {\cal G}$ be the Lie algebra of its stabilizer. Our objective is to understand points $[y]$, and their stabilizers which occur in the vicinity of $[x]$. We construct an explicit ${\cal G}$-action on a suitable neighbourhood of $x$, which we call the local model at $x$. We show that Lie algebras of stabilizers of points in the vicinity of $x$ are parameterized by subspaces of ${\cal H}$. When ${\cal H}$ is reductive these are Lie subalgebras of ${\cal H}$. If the orbit of $x$ is closed this also follows from Luna's theorem. Our construction involves a map connected to the local curvature form at $x$. We apply the local model to forms, when the form $g$ is obtained from the form $f$ as the leading term of a one parameter family acting on $f$. We show that there is a flattening ${\cal K}_0$ of ${\cal K}$, the stabilizer of $f$ which sits as a subalgebra of ${\cal H}$, the stabilizer $g$. We specialize to the case of forms $f$ whose $SL(X)$-orbits are affine, and the orbit of $g$ is of co-dimension $1$. We show that (i) either ${\cal H}$ has a very simple structure, or (ii) conjugates of the elements of ${\cal K}$ also stabilize $g$ and the tangent of exit. Next, we apply this to the adjoint action. We show that for a general matrix $X$, the signatures of nilpotent matrices in its projective orbit closure (under conjugation) are determined by the multiplicity data of the spectrum of $X$. Finally, we formulate the path problem of finding paths with specific properties from $y$ to its limit points $x$ as an optimization problem using local differential geometry. Our study is motivated by Geometric Complexity Theory proposed by the second author and Ketan Mulmuley.

preprint2020arXiv

Wreath/cascade products and related decomposition results for the concurrent setting of Mazurkiewicz traces (extended version)

We develop a new algebraic framework to reason about languages of Mazurkiewicz traces. This framework supports true concurrency and provides a non-trivial generalization of the wreath product operation to the trace setting. A novel local wreath product principle has been established. The new framework is crucially used to propose a decomposition result for recognizable trace languages, which is an analogue of the Krohn-Rhodes theorem. We prove this decomposition result in the special case of acyclic architectures and apply it to extend Kamp's theorem to this setting. We also introduce and analyze distributed automata-theoretic operations called local and global cascade products. Finally, we show that aperiodic trace languages can be characterized using global cascade products of localized and distributed two-state reset automata.

preprint2014arXiv

A Computational Framework for Boundary Representation of Solid Sweeps

This paper proposes a robust algorithmic and computational framework to address the problem of modeling the volume obtained by sweeping a solid along a trajectory of rigid motions. The boundary representation (simply brep) of the input solid naturally induces a brep of the swept volume. We show that it is locally similar to the input brep and this serves as the basis of the framework. All the same, it admits several intricacies: (i) geometric, in terms of parametrizations and, (ii) topological, in terms of orientations. We provide a novel analysis for their resolution. More specifically, we prove a non-trivial lifting theorem which allows to locally orient the output using the orientation of the input. We illustrate the framework by providing many examples from a pilot implementation.

preprint2014arXiv

A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures

We investigate a generalization of the Łoś-Tarski preservation theorem via the semantic notion of \emph{preservation under substructures modulo $k$-sized cores}. It was shown earlier that over arbitrary structures, this semantic notion for first-order logic corresponds to definability by $\exists^k\forall^*$ sentences. In this paper, we identify two properties of classes of finite structures that ensure the above correspondence. The first is based on well-quasi-ordering under the embedding relation. The second is a logic-based combinatorial property that strictly generalizes the first. We show that starting with classes satisfying any of these properties, the classes obtained by applying operations like disjoint union, cartesian and tensor products, or by forming words and trees over the classes, inherit the same property. As a fallout, we obtain interesting classes of structures over which an effective version of the Łoś-Tarski theorem holds.

preprint2014arXiv

Incorporating Sharp Features in the General Solid Sweep Framework

This paper extends a recently proposed robust computational framework for constructing the boundary representation (brep) of the volume swept by a given smooth solid moving along a one parameter family $h$ of rigid motions. Our extension allows the input solid to have sharp features, i.e., to be of class G0 wherein, the unit outward normal to the solid may be discontinuous. In the earlier framework, the solid to be swept was restricted to be G1, and thus this is a significant and useful extension of that work. This naturally requires a precise description of the geometry of the surface generated by the sweep of a sharp edge supported by two intersecting smooth faces. We uncover the geometry along with the related issues like parametrization, self-intersection and singularities via a novel mathematical analysis. Correct trimming of such a surface is achieved by a delicate analysis of the interplay between the cone of normals at a sharp point and its trajectory under $h$. The overall topology is explicated by a key lifting theorem which allows us to compute the adjacency relations amongst entities in the swept volume by relating them to corresponding adjacencies in the input solid. Moreover, global issues related to body-check such as orientation are efficiently resolved. Many examples from a pilot implementation illustrate the efficiency and effectiveness of our framework.

preprint2013arXiv

Generalizations of the Los-Tarski Preservation Theorem

We present new preservation theorems that semantically characterize the $\exists^k \forall^*$ and $\forall^k \exists^*$ prefix classes of first order logic, for each natural number $k$. Unlike preservation theorems in the literature that characterize the $\exists^* \forall^*$ and $\forall^* \exists^*$ prefix classes, our theorems relate the count of quantifiers in the leading block of the quantifier prefix to natural quantitative properties of the models. As special cases of our results, we obtain the classical Los-Tarski preservation theorem for sentences in both its extensional and substructural versions. For arbitrary finite vocabularies, we also generalize the extensional version of the Los-Tarski preservation theorem for theories. We also present an interpolant-based approach towards these results. Finally, we present partial results towards generalizing to theories, the substructural version of the Los-Tarski theorem and in the process, we give a preservation theorem that provides a semantic characterization of $Σ^0_n$ theories for each natural number $n$.

preprint2013arXiv

Local and Global Analysis of Parametric Solid Sweeps

In this work, we propose a detailed computational framework for modelling the envelope of the swept volume, that is the boundary of the volume obtained by sweeping an input solid along a trajectory of rigid motions. Our framework is adapted to the well-established industry-standard brep format to enable its implementation in modern CAD systems. This is achieved via a "local analysis", which covers parametrization and singularities, as well as a "global theory" which tackles face-boundaries, self-intersections and trim curves. Central to the local analysis is the "funnel" which serves as a natural parameter space for the basic surfaces constituting the sweep. The trimming problem is reduced to the problem of surface-surface intersections of these basic surfaces. Based on the complexity of these intersections, we introduce a novel classification of sweeps as either decomposable or non-decomposable. Further, we construct an {\em invariant} function $θ$ on the funnel which efficiently separates decomposable and non-decomposable sweeps. Through a geometric theorem we also show intimate connections between $θ$, local curvatures and the inverse trajectory used in earlier works as an approach towards trimming. In contrast to the inverse trajectory approach, $θ$ is robust and is the key to a complete structural understanding, and an efficient computation of both, the singular locus and the trim curves, which are central to a stable implementation. Several illustrative outputs of a pilot implementation are included.

preprint2012arXiv

A procedural framework and mathematical analysis for solid sweeps

Sweeping is a powerful and versatile method of designing objects. Boundary of volumes (henceforth envelope) obtained by sweeping solids have been extensively investigated in the past, though, obtaining an accurate parametrization of the envelope remained computationally hard. The present work reports our approach to this problem as well as the important problem of identifying self-intersections within the envelope. Parametrization of the envelope is, of course, necessary for its use in most current CAD systems. We take the more interesting case when the solid is composed of several faces meeting smoothly. We show that the face structure of the envelope mimics locally that of the solid. We adopt the procedural approach at defining the geometry in this work which has the advantage of being accurate as well as computationally efficient. The problem of detecting local self-intersections is central to a robust implementation of the solid sweep. This has been addressed by computing a subtle mathematical invariant which detects self-intersections, and which is computationally benign and requires only point queries.

preprint2012arXiv

Preservation under Substructures modulo Bounded Cores

We investigate a model-theoretic property that generalizes the classical notion of "preservation under substructures". We call this property \emph{preservation under substructures modulo bounded cores}, and present a syntactic characterization via $Σ_2^0$ sentences for properties of arbitrary structures definable by FO sentences. As a sharper characterization, we further show that the count of existential quantifiers in the $Σ_2^0$ sentence equals the size of the smallest bounded core. We also present our results on the sharper characterization for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the sharper characterization fails, but for which the classical Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.

preprint2010arXiv

Nash equilibria in Fisher market

Much work has been done on the computation of market equilibria. However due to strategic play by buyers, it is not clear whether these are actually observed in the market. Motivated by the observation that a buyer may derive a better payoff by feigning a different utility function and thereby manipulating the Fisher market equilibrium, we formulate the {\em Fisher market game} in which buyers strategize by posing different utility functions. We show that existence of a {\em conflict-free allocation} is a necessary condition for the Nash equilibria (NE) and also sufficient for the symmetric NE in this game. There are many NE with very different payoffs, and the Fisher equilibrium payoff is captured at a symmetric NE. We provide a complete polyhedral characterization of all the NE for the two-buyer market game. Surprisingly, all the NE of this game turn out to be symmetric and the corresponding payoffs constitute a piecewise linear concave curve. We also study the correlated equilibria of this game and show that third-party mediation does not help to achieve a better payoff than NE payoffs.

preprint2010arXiv

Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm

Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed in Kannan and Theobald (SODA 2007) and Theobald (2007). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. This technique also proves the existence, oddness and the index theorem of Nash equilibria in a bimatrix game. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on $[0,1]^k$ for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.