Tuhin Sahai
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:
- Benjamin J. Zhang
Department of Aeronautics and Astronautics Center for Computational Science and Engineering Massachusetts Institute of Technology Cambridge MA
2 shared publications - Vladimir A. Fonoberov
Bruker Nano
2 shared publications Abeynaya Gnanasekaran
RTX Technology Research Center (RTRC) 94705 Berkeley CA USA
1 shared publication- Abeynaya Gnanasekaran
SRI International
1 shared publication Adrian Ziessler
Department of Mathematics, Paderborn University, Paderborn, Germany
1 shared publicationAmit Surana
United Technologies Research Center East Hartford CT
1 shared publication
Latest Publications
- Open Access
- 28 September 2026
- Published by Elsevier in SSRN Electronic Journal
Stability of Transformers under Layer Normalization
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.
- 28 September 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessStability of Transformers under Layer Normalization
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.
- 11 September 2026
- Published by American Association for the Advancement of Science (AAAS) in Science Advances
- Vol. 12 (37)
Discovering algorithms with computational language processing
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.
- 11 September 2026
- Published by American Association for the Advancement of Science (AAAS) in Science Advances
- Vol. 12 (37)
Discovering algorithms with computational language processing
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
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 AccessOn the Emergence of Ergodic Dynamics in Unique Games
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.
- 31 January 2022
- Published by Elsevier in Journal of Computational Physics
- Vol. 456, 111025
A Koopman framework for rare event simulation in stochastic differential equations
- 31 January 2022
- Published by Elsevier in Journal of Computational Physics
- Vol. 456, 111025
A Koopman framework for rare event simulation in stochastic differential equations
- 21 July 2020
- Published by Springer Nature
- p. 183-206
Dynamical Systems Theory and Algorithms for NP-hard Problems
- 21 July 2020
- Published by Springer Nature
- p. 183-206
Dynamical Systems Theory and Algorithms for NP-hard Problems
- Open Access
Dynamical Systems Theory and Algorithms for NP-hard Problems
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.
Open AccessDynamical Systems Theory and Algorithms for NP-hard Problems
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.
- 15 July 2019
- Published by Springer Nature in Nonlinear Dynamics
- Vol. 97 (4) , 2003-2022
Continuous relaxations for the traveling salesman problem
- 15 July 2019
- Published by Springer Nature in Nonlinear Dynamics
- Vol. 97 (4) , 2003-2022
Continuous relaxations for the traveling salesman problem
- Open Access
- 1 January 2019
- Published by Wiley in Complexity
- Vol. 2019 (1)
Spectral Complexity of Directed Graphs and Application to Structural Decomposition
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.
- 1 January 2019
- Published by Wiley in Complexity
- Vol. 2019 (1)
Open AccessSpectral Complexity of Directed Graphs and Application to Structural Decomposition
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
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).
Open AccessA Chaotic Dynamical System that Paints
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).
- 27 April 2010
- Published by Springer Nature in Nonlinear Dynamics
- Vol. 62 (1-2) , 273-289
Backbone transitions and invariant tori in forced micromechanical oscillators with optical detection
- 27 April 2010
- Published by Springer Nature in Nonlinear Dynamics
- Vol. 62 (1-2) , 273-289
Backbone transitions and invariant tori in forced micromechanical oscillators with optical detection