TSTuhin Sahai

Tuhin Sahai

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Tuhin Sahai has a total of 23 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Stability of Transformers under Layer Normalization

    by Kelvin Kan, Xingjian Li, Benjamin J. Zhang, Tuhin Sahai, Stanley Osher, Krishna Kumar, Markos A. Katsoulakis

    Despite their widespread use, training deep Transformers can be unstable. Layer normalization, a standard component, improves training stability, but its placement has often been ad hoc. In this paper, we conduct a principled study on the forward (hidden states) and backward (gradient) stability of Transformers under different layer normalization placements. By utilizing discrete-time optimal control theory, our results provide key insights into the training dynamics: whether training drives Transformers toward regular solutions or pathological behaviors. For forward stability, we derive explicit bounds on the growth of hidden states in trained Transformers. For backward stability, we analyze how layer normalization affects the backpropagation of gradients, thereby explaining the training dynamics of each layer normalization placement. Our analysis also guides the scaling of residual steps in Transformer blocks, where appropriate choices can further improve stability and performance. Our numerical results corroborate our theoretical findings. Beyond these results, our framework provides a principled way to sanity-check the stability of Transformers under new architectural modifications, offering guidance for future designs.

  • Discovering algorithms with computational language processing

    by Théo Bourdais, Abeynaya Gnanasekaran, Houman Owhadi, Tuhin Sahai

    We present a framework automating algorithm discovery by bootstrapping their natural conceptualization as sequences of operations, represented as tokens. These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures. Our ensemble Monte Carlo tree search guided by reinforcement learning explores token chaining and drives the creation of new tokens via byte-pair encoding. This methodology rediscovers, improves, and generates new algorithms that substantially outperform existing methods for strongly nondeterministic polynomial-time–hard combinatorial optimization problems and foundational quantum computing approaches such as Grover’s and the quantum approximate optimization algorithm. Operating at the computational rather than code-generation level, our framework produces algorithms that can be tailored specifically to problem instances, not merely classes.

  • Open Access

    On the Emergence of Ergodic Dynamics in Unique Games

    by Tuhin Sahai, Abeynaya Gnanasekaran

    The Unique Games Conjecture (UGC) constitutes a highly dynamic subarea within computational complexity theory, intricately linked to the outstanding P versus NP problem. Despite multiple insightful results in the past few years, a proof for the conjecture remains elusive. In this work, we construct a novel dynamical systems-based approach for studying unique games and, more generally, the field of computational complexity. We propose a family of dynamical systems whose equilibria correspond to solutions of unique games and prove that unsatisfiable instances lead to ergodic dynamics. Moreover, as the instance hardness increases, the weight of the invariant measure in the vicinity of the optimal assignments scales polynomially, sub-exponentially, or exponentially depending on the value gap. We numerically reproduce a previously hypothesized hardness plot associated with the UGC. Our results indicate that the UGC is likely true, subject to our proposed conjectures that link dynamical systems theory with computational complexity.


  • Open Access

    Dynamical Systems Theory and Algorithms for NP-hard Problems

    by Tuhin Sahai

    This article surveys the burgeoning area at the intersection of dynamical systems theory and algorithms for NP-hard problems. Traditionally, computational complexity and the analysis of non-deterministic polynomial-time (NP)-hard problems have fallen under the purview of computer science and discrete optimization. However, over the past few years, dynamical systems theory has increasingly been used to construct new algorithms and shed light on the hardness of problem instances. We survey a range of examples that illustrate the use of dynamical systems theory in the context of computational complexity analysis and novel algorithm construction. In particular, we summarize a) a novel approach for clustering graphs using the wave equation partial differential equation, b) invariant manifold computations for the traveling salesman problem, c) novel approaches for building quantum networks of Duffing oscillators to solve the MAX-CUT problem, d) applications of the Koopman operator for analyzing optimization algorithms, and e) the use of dynamical systems theory to analyze computational complexity.

  • Continuous relaxations for the traveling salesman problem

    by Tuhin Sahai, Adrian Ziessler, Stefan Klus, Michael Dellnitz


  • Open Access

    Spectral Complexity of Directed Graphs and Application to Structural Decomposition

    by Igor Mezić, Vladimir A. Fonoberov, Maria Fonoberova, Tuhin Sahai

    We introduce a new measure of complexity (called spectral complexity) for directed graphs. We start with splitting of the directed graph into its recurrent and nonrecurrent parts. We define the spectral complexity metric in terms of the spectrum of the recurrence matrix (associated with the reccurent part of the graph) and the Wasserstein distance. We show that the total complexity of the graph can then be defined in terms of the spectral complexity, complexities of individual components, and edge weights. The essential property of the spectral complexity metric is that it accounts for directed cycles in the graph. In engineered and software systems, such cycles give rise to subsystem interdependencies and increase risk for unintended consequences through positive feedback loops, instabilities, and infinite execution loops in software. In addition, we present a structural decomposition technique that identifies such cycles using a spectral technique. We show that this decomposition complements the well‐known spectral decomposition analysis based on the Fiedler vector. We provide several examples of computation of spectral and total complexities, including the demonstration that the complexity increases monotonically with the average degree of a random graph. We also provide an example of spectral complexity computation for the architecture of a realistic fixed wing aircraft system.


  • Open Access

    A Chaotic Dynamical System that Paints

    by Tuhin Sahai, George Mathew, Amit Surana

    Can a dynamical system paint masterpieces such as Da Vinci's Mona Lisa or Monet's Water Lilies? Moreover, can this dynamical system be chaotic in the sense that although the trajectories are sensitive to initial conditions, the same painting is created every time? Setting aside the creative aspect of painting a picture, in this work, we develop a novel algorithm to reproduce paintings and photographs. Combining ideas from ergodic theory and control theory, we construct a chaotic dynamical system with predetermined statistical properties. If one makes the spatial distribution of colors in the picture the target distribution, akin to a human, the algorithm first captures large scale features and then goes on to refine small scale features. Beyond reproducing paintings, this approach is expected to have a wide variety of applications such as uncertainty quantification, sampling for efficient inference in scalable machine learning for big data, and developing effective strategies for search and rescue. In particular, our preliminary studies demonstrate that this algorithm provides significant acceleration and higher accuracy than competing methods for Markov Chain Monte Carlo (MCMC).