The emergence of antibiotic resistance is a major clinical challenge of the present day. To understand and predict the phenomenon, one must be able to quantitatively describe the evolutionary paths leading to resistance acquisition. I will present our contribution to this problem in two parts. In the first part, I will introduce a model based on empirical dose-response curves in which a bacterial fitness landscape changes systematically with drug concentration. The model predicts that epistasis, i.e. the interaction between mutational effects, is maximized at intermediate drug concentration. Despite the high ruggedness of the landscapes, we find the unexpected property that all fitness peaks are accessible from the wild type regardless of the concentration. We further predict that resistance evolves in two distinct phases involving the interplay of two different phenotypes, the quantitative features of the phases being determined by the drug concentration. In the second part, I will discuss the repeatability of the fixation of resistance mutations, which is a first step towards understanding the predictability of antibiotic resistance evolution. I will show how a heavy-tailed distribution of the fitness effects of mutations makes the degree of repeatability a non-self-averaging random variable. By applying this to data on resistance to the drug cefotaxime, I will demonstrate that at high concentration of the drug, the repeatability of fixation depends on the identity of resistance mutations and cannot be determined from the distribution of fitness effects alone.
Biology Seminar | IMSc Webinar
Apr 29 14:00-15:00
Manaswi Paraashar | Department of Computer Science, University of Copenhagen.
Quantum computing is currently one of the most active areas of research, mainly due to its ability to outperform classical computing for certain computational tasks. We will look at quantum computing through the lenses of two central and closely-related models of computation: query complexity and communication complexity. The majority of provable advantages of quantum computing over classical computing are found within these models, which makes them crucial. In this talk, I will discuss quantum query and communication complexity, with a focus on the role of symmetry.
Along the way I will give a brief overview of some of my results and current research interests. I will describe the problem of quantum query-to-communication simulation. It is a well-known fact that classical query algorithms for an n-bit Boolean function can be simulated to give communication protocols of a related communication problem with only a constant overhead. Buhrman, Cleve and Wigderson (STOC'98) showed that this query-to-communication simulation can also be performed in the quantum world, however, with an O(log n) overhead. Whether this overhead is necessary was a long-standing open problem. We resolve this open problem, with symmetry associated with Boolean functions playing a central role. We will also explore how symmetry affects the relationship between complexity measures of Boolean functions and can be exploited in designing quantum algorithms for computing over noisy data.
This talk is based on an ongoing work and the following papers:
- Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande and Manaswi Paraashar. QIP 2020 and CCC 2020.
- Symmetry and Quantum Query-to-Communication Simulation. Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil S. Mande, Manaswi Paraashar and Ronald de Wolf. STACS 2022.
- Separations Between Combinatorial Measures for Transitive Functions. Sourav Chakraborty, Chandrima Kayal and Manaswi Paraashar. ICALP 2022.
- Randomized and quantum query complexities of finding a king in a tournament. Nikhil S. Mande, Manaswi Paraashar and Nitin Saurabh. FSTTCS 2023.
- Local Correction of Linear Functions over the Boolean Cube. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan and Madhu Sudan. STOC 2024.
- On the communication complexity of finding a king. Nikhil Mande, Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh. Manuscript. 2024.