Indian Institute of Science Bangalore
etd@IISc Electronic Theses and Dissertations at Indian Institute of ScienceNot a member yet
6204 research outputs found
Sort by
Regional and Local-scale Analysis of Landslides Induced by Rainfall and Earthquakes
No full textLandslides are major natural disasters which pose a significant risk to lives and infrastructure globally. As urbanization is increasing due to the increasing population in mountainous regions, the risk due to landslides draws grave concern owing to the damage and disruption since the last decade. Hence, regional-scale and local-scale landslide analyses are necessary to reduce the impact of landslides on lives and infrastructure; and efficiently prevent the landslide risk. The landslide analysis must be conducted separately for different triggering factors as the slope materials follow different failure mechanisms under various triggering factors. In this thesis, efficient models for landslide analysis at regional-scale as well as local-scale are developed, focusing mainly on understanding the relationship between actuating factors and slope failure events; and the slope failure mechanism. These models are developed for different causal factors, including rainfall and earthquakes.
For regional scale analysis of landslides, a methodology is introduced for landslide mapping, which aims at the accurate and faster demarcation of slope areas affected by landslides. Fast and accurate landslide mapping forms the basis of research and practice of landslide hazard and risk analysis. A systematic framework is also presented to estimate landslide hazard at regional-scale using previous landslide incidents and establish a relationship between different triggering factors and landslide incidents. Further, a predictive model is proposed to estimate the evolution of seismically induced slope displacement with time. The developed model is based on the dynamic response surface method (DRSM). Various methodologies are proposed for local-scale analysis of slope systems under various causal factors, i.e., rainfall and earthquakes to estimate the uncertainty in soil parameters using probabilistic methods and machine learning algorithms. Several algorithms are developed and implemented in Python and MATLAB to add new features that introduce complexity in the numerical models and interface the deterministic and probabilistic analysis.
Overall, it is anticipated that the work presented in this thesis will facilitate guidelines for 1) landslide inventory and hazard mapping due to rainfall infiltration, 2) estimation of evolution of seismically-induced slope displacement with time using predictive models, and 3) probabilistic back analysis of slope system under various causal factors
Enabling Lithium Metal Anode for Garnet Electrolyte based Solid State Batteries
No full textSolid-state lithium metal batteries (SSLMB) employing inorganic solid electrolytes (ISE) in conjunction with lithium metal anode and intercalation cathode are considered among the most promising alternatives for Li-ion batteries1. Li-metal is an optimal choice of anode because of its high gravimetric and volumetric energy density. ISE, along with being flame-retardant, has a superior tolerance for a wide operating temperature range (−30 to 100 °C) while delivering a reliable performance2. The high shear modulus of ISE is also expected to mechanically suppress lithium dendrite growth3, thus enabling high energy density batteries. However, lithium dendrite penetration at current densities as low as 50 µA/cm2 was observed in SSLMBs4, while current densities of ≥1mA/cm2 are desired for practical use. The microscopic mechanisms that lead to lithium dendrite growth in SSLMBs are still unclear. Furthermore, the poor electrode/electrolyte interface coupled with processing challenges of ISEs have thwarted their realization as a practical battery system5.
In the present work, we investigate dendrite growth through ISE, one of the most fundamental challenges with SSLMBs. First, for the choice of ISE, we synthesized Li6.4La3Zr1.4Ta0.4O12 (LLZTO), a garnet-type fast Li-ion conducting oxide. We interface lithium metal to this ISE via a well-known approach of employing a lithium alloying interlayer in between lithium metal and ISE. However, cells fabricated using aluminium interlayer show signs of dendrite growth at a current density of <300 µA/cm2. Through a set of electrochemical and scanning electron microscopy (SEM) techniques, we observed that interfacial voids at Li/LLZTO interface precede dendrite nucleation and growth. We believe that the edges of these voids can act as a favourable nucleation site for dendrites. Using a simple electrostatic model, we show that current density at the edges of the voids could be amplified by as much as four orders of magnitude, making the cells highly susceptible to dendrite growth after void formation. By employing standard pattering to induce controlled discontinuities, we further confirm our hypothesis by showing selective dendrite growth along the edges of discontinuities6.
Based on the above observations, we developed strategies to increase the tolerance for dendrite growth in these battery systems. We note that the aluminium interlayer will dissolve with lithium metal over time, making the interface susceptible to discontinuities, as observed in cells without interlayers. Hence, if a material that doesn’t alloy with lithium while also fulfilling the criteria of an interlayer is used, it can enhance the current densities for dendrite nucleation. Based on this, we employed tungsten (W) as an interlayer material. We observed that current densities for dendrite nucleation in W interlayer cells were ≥ 530 µA/cm2, nearly twice that of Al-interlayer cells. Computational calculations showed that lithium vacancy migration energies, which is the first step for void formation, were 2-5 times higher for W surface than for Al surface, further confirming our observation6.
Increasing the structural density of LLZTO ISE further improved the current density to 1 mA/cm2. Finally, we explored the anode-free battery configuration, which employs in-situ generated metallic lithium anode without a need for lithium handling, a significant processing advantage for wide-scale production of SSLMBs. Our work is an essential step in realizing a practical SSLMB whilst gaining mechanistic insights into dendrite growth in these energy storage systems
Multi-Armed Bandits – On Range Searching and On Slowly-varying Non-stationarity
No full textMulti-Armed Bandits (MAB) is a popular framework for modelling sequential decision-making problems under uncertainty. This thesis is a compilation of two independent works on MABs.
1. In the first work, we study a multi-armed bandit (MAB) version of the range-searching problem. In its basic form, range searching considers as input a set of points (on the real line) and a collection of (real) intervals. Here, with each specified point, we have an associated weight, and the problem objective is to find a maximum-weight point within every given interval.
The current work addresses range searching with stochastic weights: each point corresponds to an arm (that admits sample access), and the point’s weight is the (unknown) mean of the underlying distribution. In this MAB setup, we develop sample-efficient algorithms that find, with high probability, near-optimal arms within the given intervals, i.e., we obtain PAC (probably approximately correct) guarantees. We also provide an algorithm for a generalization wherein the weight of each point is a multi-dimensional vector. The sample complexities of our algorithms depend, in particular, on the size of the optimal hitting set of the given intervals.
Finally, we establish lower bounds proving that the obtained sample complexities are essentially tight. Our results highlight the significance of geometric constructs— specifically, hitting sets—in our MAB setting.
2. In the second work, we consider minimisation of dynamic regret in non-stationary bandits with a slowly varying property. Namely, we assume that arms’ rewards are stochastic and independent over time, but that the absolute difference between the expected rewards of any arm at any two consecutive time-steps is at most a drift limit δ > 0. For this setting that has not received enough attention in the past, we give a new algorithm which extends naturally the well-known Successive Elimination algorithm to the non-stationary bandit setting. We establish the first instance-dependent regret upper bound for slowly varying non-stationary bandits. The analysis in turn relies on a novel characterization of the instance as a detectable gap profile that depends on the expected arm reward differences. We also provide the first minimax regret lower bound for this problem, enabling us to show that our algorithm is essentially minimax optimal. Also, this lower bound we obtain matches that of the more general total variation-budgeted bandits problem, establishing that the seemingly easier former problem is at least as hard as the more general latter problem in the minimax sense. We complement our theoretical results with experimental illustrations
Studies on BODIPY Appended Ruthenium(II) Complexes for Bioimaging and Photodynamic Therapy Applications
No full textPhotodynamic therapy (PDT) is a medical technique that utilizes light, oxygen, and a photosensitizer to treat several medical conditions, including cancer. Because of the limitations and side effects of traditional anticancer therapies like surgery, chemotherapy, and radiation therapy, PDT has been recognized as an adjuvant and, in some cases, a mainstream alternative. Currently, clinical PDT utilizes tetrapyrrolic photosensitizers that possess several drawbacks. Even worldwide approved gold standard photosensitizer Photofrin® requires a high dose for the therapeutic effect that results in undesirable side effects like skin sensitivity and hepatotoxicity. In recent years, transition metal complexes are gaining interest as new photosensitizers with their fine-tuned photophysical and biological properties. This thesis work presents the results from a systematic study on the design and synthesis of new boron-dipyrromethene (BODIPY) appended ruthenium(II)complexes to study their photoinduced reactive oxygen species (ROS) generation ability, light-induced cytotoxicity and cellular imaging ability.
Here, a wide range of ruthenium coordination units are connected to BODIPY chromophore with various linkers, and their effect on photophysical and photobiological properties investigated. New ruthenium(II) complexes with formulations [Ru(L1/2)(L3/4)Cl]Cl where L1, L2 (having biotin) are NN-donor bidentate phenanthroline derivatives and L3, L4 (contain BODIPY) are NNN-donor tridentate dipicolylamine derivative, were synthesized, characterized and their photocytotoxicity evaluated. The complex having both BODIPY and cancer targeting biotin showed cancer cells elective PDT effect giving respective IC50 value of 0.98±0.04 and 3.9±0.4 μM in A549 (lung cancer) and HPL1D (noncancerous) cell lines in visible light of 400-700 nm, while being non-toxic in the dark. Analogous complexes containing di-styryl BODIPY were prepared and their PDT activity with redlight activation was evaluated. The active complex produced a remarkable photocytotoxicity index (PI, ratio of IC50 in dark and with light exposure) of >5000 with red light (600- 720 nm) activation. Next, a series of bichromophoric systems having a heteroleptic [Ru(tpy)2] (tpy = terpyridine) moiety covalently linked to a BODIPY pendant were prepared, characterized and their photophysical and photobiological properties were evaluated. In a following study, a series of biotin-conjugated compounds containing BODIPY or Ru(II)-bis-tpy or both chromophoric units were developed and the difference of multichromophoric Ru-BODIPY conjugates with structurally similar compounds having a single chromophore were investigated highlighting the importance of constructing such bichromophoric systems. These bichromophoric systems produced both superoxide and singlet oxygen via dual type-I/II photosensitization processes and exerted potent apoptotic PDT effect with visible light activation. Finally, two homoleptic complexes with formulation [Ru(tpy-BODIPY)2]Cl2,where the connection between the BODIPY unit and the Ru(II)-bis-tpy scaffold differs by a phenylacetylene spacer, were prepared as PDT agents with simple molecular design and the effect of the spacer was studied in terms of structure-activity relationship. In summary, this thesis work presents systematic developments of Ru(II)-BODIPY conjugates as novel photosensitizers and photodetection agents for phototherapeutic applications
Reinforcement Learning Algorithms for Off-Policy, Multi-Agent Learning and Applications to Smart Grids
No full textReinforcement Learning (RL) algorithms are a popular class of algorithms for training an agent to
learn desired behavior through interaction with an environment whose dynamics is unknown to the
agent. RL algorithms combined with neural network architectures have enjoyed much success in various
disciplines like games, medicine, energy management, economics and supply chain management.
In our thesis, we study interesting extensions of standard single-agent RL settings, like off-policy and
multi-agent settings. We discuss the motivations and importance of these settings and propose convergent
algorithms to solve these problems. Finally, we consider one of the important applications of
RL, namely smart grids. The goal of the smart grid is to develop a power grid model that intelligently
manages its energy resources. In our thesis, we propose RL models for efficient smart grid design.
Learning the value function of a given policy (target policy) from the data samples obtained from
a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This
problem is studied under the setting of off-policy prediction. Temporal Difference (TD) learning
algorithms are a popular class of algorithms for solving prediction problems. TD algorithms with
linear function approximation are convergent when the data samples are generated from the target
policy (known as on-policy prediction) itself. However, it has been well established in the literature
that off-policy TD algorithms under linear function approximation may diverge. In the first part of the
thesis, we propose a convergent online off-policy TD algorithm under linear function approximation.
The main idea is to penalize updates of the algorithm to ensure convergence of the iterates. We provide
a convergence analysis of our algorithm. Through numerical evaluations, we further demonstrate the
effectiveness of our proposed scheme.
Subsequently, we consider the “off-policy control” setup in RL, where an agent’s objective is to
compute an optimal policy based on the data obtained from a behavior policy. As the optimal policy
can be very different from the behavior policy, learning optimal behavior is very hard in the “offpolicy”
setting compared to the “on-policy” setting wherein the data is collected from the new policy
updates. In this work, we propose the first deep off-policy natural actor-critic algorithm that utilizes
state-action distribution correction for handling the off-policy behavior and the natural policy gradient
for sample efficiency. Unlike the existing natural gradient-based actor-critic algorithms that use only
fixed features for policy and value function approximation, the proposed natural actor-critic algorithm
can utilize a deep neural network’s power to approximate both policy and value function. We illustrate
the benefit of the proposed off-policy natural gradient algorithm by comparing it with the Euclidean
gradient actor-critic algorithm on benchmark RL tasks.
In the third part of the thesis, we consider the problem of two-player zero-sum games. In this
setting, there are two agents, both of whom aim to optimize their payoffs. Both the agents observe
the same state of the game, and the agents’ objective is to compute a strategy profile that maximizes
their payoffs. However, the payoff of the second agent is the negative of the payoff obtained by the
first agent. Therefore, the objective of the second agent is to minimize the total payoff obtained by
the first agent. This problem is formulated as a min-max Markov game in the literature. In this work,
we compute the solution of the two-player zero-sum game utilizing the technique of successive relaxation.
Successive relaxation has been successfully applied in the literature to compute a faster value
iteration algorithm in the context of Markov Decision Processes. We extend the concept of successive
relaxation to the two-player zero-sum games. We then derive a generalized minimax Q-learning
algorithm that computes the optimal policy when the model information is unknown. Finally, we
prove the convergence of the proposed generalized minimax Q-learning algorithm utilizing stochastic
approximation techniques. Through experiments, we demonstrate the advantages of our proposed
algorithm.
Next, we consider a cooperative stochastic games framework where multiple agents work towards
learning optimal joint actions in an unknown environment to achieve a common goal. In many realworld
applications, however, constraints are often imposed on the actions that the agents can jointly
take. In such scenarios, the agents aim to learn joint actions to achieve a common goal (minimizing a
specified cost function) while meeting the given constraints (specified via certain penalty functions).
Our work considers the relaxation of the constrained optimization problem by constructing the Lagrangian
of the cost and penalty functions. We propose a nested actor-critic solution approach to
solve this relaxed problem. In this approach, an actor-critic scheme is employed to improve the policy
for a given Lagrange parameter update on a faster timescale as in the classical actor-critic architecture.
Using this faster timescale policy update, a meta actor-critic scheme is employed to improve the
Lagrange parameters on the slower timescale. Utilizing the proposed nested actor-critic scheme, we
develop three Nested Actor-Critic (N-AC) algorithms.
In recent times, actor-critic algorithms with attention mechanisms have been successfully applied
to obtain optimal actions for RL agents in multi-agent environments. In the fifth part of our thesis,
we extend this algorithm to the constrained multi-agent RL setting considered above. The idea here
is that optimizing the common goal and satisfying the constraints may require different modes of
attention. Thus, by incorporating different attention modes, the agents can select useful information
required for optimizing the objective and satisfying the constraints separately, thereby yielding better
actions. Through experiments on benchmark multi-agent environments, we discuss the advantages of
our proposed attention-based actor-critic algorithm.
In the last part of our thesis, we study the applications of RL algorithms to Smart Grids. We
consider two important problems - on the supply-side and demand-side, respectively, and study both in
a unified framework. On the supply side, we study the problem of energy trading among microgrids to
maximize profit obtained from selling power while at the same time satisfying the customer demand.
On the demand side, we consider optimally scheduling the time-adjustable demand - i.e., of loads
with flexible time windows in which they can be scheduled. While previous works have treated these
two problems in isolation, we combine these problems and provide a unified Markov decision process
(MDP) framework for these problems
Operating System Support for Efficient Virtual Memory
No full textComputers rely on the virtual memory abstraction to simplify programming, portability, physical memory management and ensure isolation among co-running applications. However, it creates a layer of indirection in the critical path of execution wherein the processor needs to translate an application-generated virtual address into the corresponding physical address before performing the computation. To accelerate the virtual-to-physical address translation, processors cache recently used addresses in Translation Lookaside Buffers (TLBs).
Unfortunately, modern data-centric applications executing on large memory servers experience frequent TLB misses. The processor services TLB misses by walking the in-memory page tables that often involves accessing physical memory. Consequently, the processor spends 30-50% of total cycles in servicing TLB misses alone for many big-data applications. Virtualization and non-uniform memory access (NUMA) architectures in multi-socket servers further exacerbate this overhead. Virtualization adds an additional level of address translation while NUMA can increase the latency of accessing page tables residing on a remote socket. The address translation overhead will increase further with deeper page tables and multi-tiered memory systems in newer and upcoming systems. In short, virtual memory is showing its age in the era of data-centric computing.
In this thesis, we propose ways to moderate the overhead of virtual-to-physical address translation. The majority of this thesis focuses on huge pages. Processor designers have invested significant hardware in supporting huge pages to reduce the number and cost of TLB misses e.g., x86 architecture supports 2MB and 1GB huge pages. However, we find that operating systems often fail to harness the full potential of huge pages. This thesis highlights the pitfalls associated with the current huge page management strategies and proposes various operating system enhancements to maximize the benefits of huge pages. We also address the effect of non-uniform memory accesses on address translation with NUMA-aware page table management.
A key objective of this thesis is to avoid modifying the applications or adding new features to the hardware. Therefore, all the solutions discussed in this thesis apply to current hardware and remain transparent to the applications. All of our contributions are open-sourced
A Study of the X-ray Variability and Accretion Mechanism in High Mass X-ray Binary Pulsars
No full textHigh-mass X-ray binaries are among the most luminous X-ray sources. They host an accreting compact object (more often a neutron star) and a massive (M > 10 M⊙) donor star. They are among the earliest discovered X-ray sources and are essential for various astrophysical contexts ranging from high energy astrophysics, stellar evolution, and knowledge of gravitational wave progenitors. They show variation in the X-ray intensity on all timescales ranging from seconds to days or months, which carry information about the underlying accretion mechanisms and their immediate environment. We have observed the X-ray variability in some of such sources and provided the possible physical pictures behind them.
Firstly, we have investigated a unique partial eclipse seen in IGR J16393-4643. Unlike other HMXBs, IGR J16393-4643 shows a partial eclipse with ∼25% of total intensity when observed with Swift-BAT making it the only partially eclipsing candidate in the HMXB catalog. We have presented the results from our spectroscopic study, which indicates that the low-intensity state might not be an eclipse, as previously thought, but absorption in the stellar corona.
In the second part, we studied a Be X-ray binary GRO J2058+42 that went through a Type-II outburst during March-April 2019, lasting for about 50 days. With this unique opportunity, we could analyze the broadband characteristics of the pulsar using three NuSTAR observations during the outburst and quiescent for the first time and the accretion torque characteristics of the pulsar over a range of X-ray luminosity.
Lastly, We have discussed the spin evolution of accreting persistent X-ray pulsars. The process of transfer of the accretion torque in the wind-fed persistent pulsar is complex and does not have a clear correlation with the mass accretion rate. A possible explanation of such torque behavior can be the change in the accretion mode and geometry. In this work, we have used the pulse profiles of four wind-fed pulsars as a tool to observe any changes in the accretion geometry at different accretion torque
Diabetogenesis and Albumin Molecular Modifications Newer Biological Insights and Clinical Implications
No full textTo address the many unmet scientific needs in diabetes care (pathogenesis pathways, earliest diagnosis, efficient monitoring, safer and better therapies and importantly prevention approaches), our research focussed on: (a) diabetogenesis and biomarkers and (b) albumin molecular modifications. Establishment of the “Samatvam – Indian Institute of Science” prospective longitudinal cohort, supported by a well annotated biobank repository and a robust cloud based electronic medical record platform, provided the foundation for this translational scientific endeavour.
Initially, the "IISc - PathShodh" electrochemistry technology based multianalyte point of care device (POC: anuPath) for selected diabetes biomarkers (HbA1c, hemoglobin, serum albumin, urine albumin and urine creatinine) was validated by simultaneous comparison with “gold standard” conventional laboratory assays. Health worker-based community implementation of this “lab – on – palm”, confirmed its utility both for “in-clinic” diabetes care and “remote” health monitoring.
Insulin resistance and beta-cell dysfunction, both genetic and environment determined, are the core defects of type 2 diabetes. Together they result in cell, tissue, vascular and organ damage in diabetes, through multiple deranged biochemical pathways, including pathological protein modifications like glycation and oxidation. Our studies on diabetogenesis highlighted the increased prevalence of insulin resistance (HOMA IR) and beta-cell dysfunction (HOMA B%) (i.e., compensatory hyperinsulinemia) even in the earliest stage of normal glucose tolerance (NGT). This pathogenetic profile was associated with increasing adiposity (i.e., overweight and obesity). This “healthy” (NGT) stage was also already marked by multiple abnormalities related to chronic inflammation, atherogenesis and other aspects of dysmetabolism. Our data indicated for the first time, that insulin resistance is one of the independent determinants of the prognostically useful “glycation gap” (GG). Thus, insulin resistance might be a mechanism for the reported association of higher (positive) GG with various microvascular and macrovascular diabetes complications and even increased mortality.
Albumin, the most abundant and physiologically vital serum protein, accumulates a range of chemical modifications (glycation, oxidation and truncation) as a consequence of its interactions with a large number of reactive small molecules which are formed or increased under conditions of abnormal pathology. Our investigations on albumin glycation, oxidation and truncation (mass spectrometry), in all stages in the evolution and progression of type 2 diabetes ("normoglycemia", prediabetes – obesity and overt diabetes), as well as in type 1 diabetes and in diabetes chronic kidney disease, yielded many novel biological and clinical insights. The common and distinctive features and mechanisms of albumin glycation and hemoglobin glycation were highlighted. Knowledge on the pathologic and clinical relevance and associations of albumin oxidation were further advanced. The potential diagnostic and prognostic significance of albumin truncation (reduction or “deficiency”) in diabetes was identified. During the course of diabetes therapy (upto 280 days), many subjects exhibited albumin glycation and albumin cysteinylation discordance, illuminating that the current “glucose-centric” only approaches to diabetes care are inadequate and incomplete and albumin cysteinylation needs independent therapeutic intervention in diabetes care. HNA2 and HNA2/eGFR index, as defined, showed potential as additional biomarkers of declining renal function, beginning at the earliest stages (including stage 1 hyperfiltration).
The many novel biological and clinical insights generated by our studies have fostered: (a) future identification of novel biomarkers battery (“diabetome”, “diabetomics”, “albuminomics”) driven diverse “healthy”, prediabetes, obesity and type 2 diabetes phenotypes and (b) discovery of better diagnostic, therapeutic and even preventive approaches for diabetes and related disorders (towards “Precision Medicine”).Indian Institute of Science, Bangalore; IMPRINT Grant Government of India; Samatvam: Science and Research for Human Welfare Trust, Bangalor
On symmetries of and equivalence tests for two polynomial families and a circuit class
No full textTwo polynomials f, g ∈ F[x1, . . . , xn] over a field F are said to be equivalent if there exists an
n×n invertible matrix A over F such that g = f(Ax), where x = (x1 · · · xn)T . The equivalence
test (in short, ET) for a polynomial family {fm}m∈N (similarly, a circuit class C ) is the following
algorithmic problem: Given input black-box access to g ∈ F[x1, . . . , xn], determine whether
there exists an f ∈ {fm}m∈N (respectively, a circuit C ∈ C ) such that g = f(Ax) (respectively,
g = C(Ax)) for some n × n invertible matrix A over F. If the answer is yes, it also outputs
an f ∈ {fm}m∈N (respectively, a circuit C ∈ C ) and an n × n invertible certificate matrix A
over F such that g = f(Ax) (respectively, g = C(Ax)). In this thesis, we study equivalence
tests for two polynomial families, namely the families of Nisan-Wigderson design polynomials
(in short, NW) and determinant, and a circuit class, namely the class of regular read-once
arithmetic formulas. In the process of designing ET for NW, we prove some fundamental
structural and algorithmic results related to the symmetries of NW, namely characterization by
symmetries, characterization by circuit identities, a circuit testing algorithm and a flip theorem.
An invertible matrix A is called a symmetry of NW if NW = NW(Ax).
In the first work, we study some useful properties of the symmetries of NW. NW is an
important polynomial in algebraic complexity theory (ACT) as it has been used to prove lower
bounds for various classes of arithmetic circuits. Similar to NW, other polynomials like the
determinant, the permanent, the IMM, etc. have also been used in many lower bound proofs
in ACT. Unlike these polynomials, which are well-studied, not much is known about NW. The
family of NW is in VNP but it is not known whether it is in VP and or is VNP-complete. In
this work, we fill in some gaps in our understanding of NW by answering certain interesting
questions related to the symmetries of NW. These questions are quite relevant from the context
of geometric complexity theory and have been studied for the permanent. We show that NW
is characterized by its symmetries over C but not over R and Q. Using the symmetries of NW,
we show that NW is characterized by circuit identities over any field. By exploiting the second
property, we give a randomized polynomial time circuit testing algorithm and a flip theorem
for NW. A circuit testing algorithm checks whether a given circuit computes NW and hence
is a natural special case of ET for NW. A circuit testing algorithm is also required for the
ET for NW. We give a randomized polynomial time reduction from general ET for NW to the
block-permuted ET for NW. Further, we also give a randomized polynomial time algorithm for
a special case of block-permuted ET for NW, which we call block-diagonal permutation scaling
ET for NW. These structural and algorithmic results crucially use some special symmetries of
NW as well as the structure of the group of symmetries of NW, denoted GNW. The structure of
GNW was studied in the author’s master’s thesis [Gup17] and is not included in this thesis.
In the second work, we study ET for the family of determinant (in short, DET) over finite
fields and over Q. A randomized polynomial time DET over C was given in [Kay12]. A randomized
polynomial time DET over a finite field Fq was given in [KNS19], which outputs a
certificate matrix over a degree n extension field of Fq, provided the input polynomial is equivalent
to the n × n determinant, denoted Detn. In this work, we give a randomized polynomial
time DET over Fq, which outputs a certificate matrix over the base field. We also give the first
randomized DET over Q, which takes oracle access to an integer factoring algorithm (IntFact),
and outputs a certificate matrix over Q. This DET runs in polynomial time in the Turing
machine model if n is bounded. If we remove oracle access to IntFact from DET over Q, then
we get a polynomial time randomized DET for every n, but it outputs a certificate matrix over
an extension field L of Q, where [L : Q] ≤ n. The heart of these algorithms is a randomized
polynomial time reduction from DET to the full matrix algebra isomorphism (FMAI) problem.
This reduction exploits the rich structure of the Lie algebra of the determinant and works over
almost every field. FMAI is a well-studied problem in computer algebra and FMAI algorithms
are known over finite fields and Q. We prove that assuming the Generalized Riemann Hypothesis,
there exists a randomized polynomial time reduction from integer factoring to DET for
quadratic forms over Q (i.e., n = 2 case). This shows that it is unlikely to get rid of the IntFact
oracle from DET over Q. We also give a reduction from FMAI to DET over almost every field,
which is efficient if n is bounded. This shows that FMAI and DET are randomized polynomial
time reducible to each other whenever n is bounded.
In the third work, we give the first randomized polynomial time equivalence test with
oracle access to quadratic form equivalence (QFE) for the class of regular read-once arithmetic
formulas (in short, regular ROFs). An arithmetic formula C over a field F is said to be read-once
if every leaf node of C is labelled by either a distinct variable or a constant from F. ROFs are
well-studied in the literature. An ROF C is called regular if every variable in C is a child of a ×
gate. Thus, the class of regular ROFs is a natural subclass of ROFs. An ET for regular ROFs
significantly generalizes QFE over C and ET algorithms for two previously studied sub-classes of
regular ROFs, namely the classes of sum-product polynomials and ROANFs. Equivalence tests
for these two classes were given recently in [MS21]. Our ET algorithm is based on some useful
properties of the Hessian determinant of a regular ROF like its non-zeroness, knowledge of its
factors and its essential variables. The arbitrary nature of the underlying tree of a regular ROF
makes the analysis of the above mentioned properties of its Hessian determinant technically
challenging. We overcome this challenge by studying the structures and coefficients of some
nice monomials in the Hessian determinant of a regular ROF
Underwater Acoustic Communications: Algorithms for Delay-Scale Spread Wideband Channels
No full textIn wideband wireless communication systems, the relative motion of the transmitter, receiver, or scatterers in the medium causes the Doppler effect, which stretches or compresses the transmitted waveforms, resulting in inter-symbol interference and a consequent severe performance degradation. To counter this, specialized transmitter and receiver architectures are needed for energy- and spectrally-efficient communications in channels characterized by path-dependent delays and time-scales. In this thesis, we develop and evaluate improved receiver side signal processing algorithms for two existing modulation schemes used in wideband Underwater Acoustic (UWA) communications. We also propose new modulation schemes suited for wideband delay and scale spread UWA channels.
In the first part of the thesis, for the well known Orthogonal Frequency Division Multiplexing (OFDM) waveform, we develop a two-stage iterative algorithm at the receiver that alternates between sparse channel estimation and data detection. Specifically, we consider the sequence of observations from partial interval demodulators (PIDs) using a partial-length Fast Fourier Transform (FFT). We show that the PID outputs help in tracking the channel by providing additional measurements to estimate the Inter-Carrier Interference (ICI) due to the Doppler spread. We also derive the Cram ́er-Rao lower bound on the mean squared error in channel estimation, and empirically show that the two-stage algorithm meets the bound at high SNR.
Next, we develop a new Bayesian-inspired data detection algorithm in the context of sweep spread carrier (S2C) communication – a practically successful waveform used in some commercial underwater acoustic modems. The existing schemes for data detection – based on the gradient heterodyne receiver – are only effective when the path delay and Doppler spread are moderate. Based on the principle of variational Bayes’ inference, we present a new variational soft symbol decoding (VSSD) algorithm. In harsh UWA channels where the existing S2C receivers completely fail, or must compromise on the data rate to maintain the bit error rate (BER) performance, the VSSD algorithm successfully recovers the data symbols, even at low signal-to-noise ratios (SNRs).
We then turn to developing a new modulation scheme for the wideband doubly spread channel, namely, Orthogonal Delay Scale Space (ODSS), from first principles. The scheme pre-processes the information symbols using a 2D ODSS transform, which performs a discrete Fourier transform on the frequency axis and inverse Mellin transform on the Mellin variable axis, to obtain the transformed symbols in the delay-scale domain. These transformed symbols are mounted onto ODSS modulation waveforms to generate the signal to be transmitted. The pre-processing step spreads the symbols in the delay-scale domain, which in turn improves the bit error rate compared to Orthogonal Time Frequency Space (OTFS) and OFDM in wideband time-varying channels. More importantly, since the ODSS modulation renders the channel matrix near-diagonal, it performs well even under low-complexity subcarrier-by-subcarrier equalization in the delay-scale domain followed by symbol recovery in the Mellin-Fourier domain.
Finally, we develop a novel Variable Bandwidth Multicarrier (VBMC) waveform comprising of multiple subcarriers that are constructed from chirp pulses. The chirps occupy progressively increasing, frequency-dependent bandwidth from the lower to upper frequency edge of the communication band. Due to this, the subcarriers maintain their near mutual orthogonality even after passing through a delay and scale spread channel. We compare the performance of VBMC with existing waveforms using a generic framework for modeling delay-scale spread channels that we develop for the first time in this thesis.
Overall, this thesis develops advanced receiver processing techniques and novel modulation schemes that greatly outperform the state-of-the-art in wideband delay-scale spread channels, while matching their performance in more benign channels