Abstract

Scientific applications like aircraft-design and machine-learning algorithms involve solving a system of linear equations. LU decomposition is helpful if the system needs to be solved repeatedly for the same Coefficient matrix but for different Constants of a Linear Equation. It also aids in other matrix operations, such as computing the determinant and inverse of a matrix. This thesis proposes an architecture of hardware accelerator for computing the LU decomposition of an input matrix. Our accelerator consists of two simple linear arrays of Processing Engines (PEs), one on each of the two SLR regions of the FPGA. All the computations arising from the block LU decomposition are simplified and scheduled on these two PE arrays. On an Alveo U50 FPGA, our design achieves a peak floating-point performance of 128 GLOPS/s and an average performance of 95 GFLOPS/s. We achieve ≈ 15× speedup on latency compared to an Intel MKL implementation on a 4-core Intel Xeon CPU.

Abstract

In this thesis two problems have been considered. The first one is related to the structure of higher order MDS codes which are a generalization of traditional MDS codes and the second one is related to distributed multi-user secret sharing. When data is transmitted over noisy channels, errors can occur, corrupting the received information. Traditional error-correcting codes like Reed-Solomon or Hamming codes are designed to correct a specific number of errors. However, they have a limitation that they can only correct up to a certain number of errors beyond which they fail to recover the original message. In many scenarios, such as wireless communication or storage systems, the number of errors can be quite high, and standard error-correction techniques might not be sufficient. This is where list decoding, proposed independently by Elias and Wozencraft, comes into play. Instead of trying to pinpoint the exact original message, list decoding provides a list of possible messages that could have been transmitted. By doing so, it offers a more flexible and robust approach to error correction, allowing for a higher number of correctable errors. The decoding radius is the maximum number of errors that can be corrected by the code. By increasing the decoding radius and allowing for a list of possible codewords, list decodable codes can handle a higher number of errors and provide a more robust approach to error correction. In a recent work by Shangguan and Tamo, an upper bound on the size of a list deocodable codes, called the Generalized Singleton bound, is derived for a given list size and decoding radius. The codes which meet this bound with equality are optimally list decodable codes. In our first problem, we study a recently introduced class of higher order MDS codes which are closely related to the optimally list decodable codes. For certain parameter regimes, we identify conditions under which performing expurgation and shortening (see Section 2.2) like operations on the higher order MDS codes based on Reed-Solomon codes obtained using Vandermonde matrix results in new higher order MDS codes with a related set of parameters. More specifically, we identify the conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes via various techniques where (n, k)-MDS(ℓ) codes denote higher order MDS codes of length n, dimension k and order ℓ ≥ 1. We also obtain a new field size upper bound for the existence of such codes which arguably improves over the best known existing bound in some parameter regimes. We believe that these results will aid in efficient constructions of higher order MDS codes. In the second problem, we focus on a Distributed Multi-User Secret Sharing (DMUSS) problem. Distributed Multi-User Secret Sharing is motivated by the need for secure and efficient ways to share sensitive information among multiple users in a decentralized manner. The traditional secret sharing scheme involves a single dealer dividing a secret into shares and distributing them among a group of users. However, this centralized approach has limitations, especially when dealing with large-scale systems or scenarios with multiple secrets and a large number of users. In DMUSS, each user can request access to a specific subset of secrets. This access control mechanism ensures that users only gain access to the secrets they are authorized to see. In this thesis we consider a DMUSS setting involving a dealer, n storage nodes and m secrets. Each user requests a subset of t out of the m secrets. Previous work in this setting addressed the case of t = 1 which we extend to handle general values of t. The users download shares from storage nodes based on the access structure and reconstruct their secrets. We establish a necessary condition on the access structure to ensure certain privacy conditions. Additionally, we establish a connection between access structures and disjunct matrices which are majorly used in the Group testing. In the Distributed Secret Sharing Protocol proposed for our setting, we utilize various disjunct matrix constructions and compare their performance in terms of the number of storage nodes and communication complexity. Moreover, we derive bounds on the optimal communication complexity of a distributed secret sharing protocol.

Abstract

Autonomous camera systems are vital in capturing dynamic events and creating engaging videos. However, existing filtering techniques used to stabilize and smoothen camera trajectories often fail to replicate the natural behavior of human camera operators. To address these challenges, our work proposes novel approaches for real-time camera trajectory optimization and gaze-guided video editing. We introduce two online filtering methods: CineConvex and CineCNN. CineConvex utilizes a sliding window-based convex optimization formulation, while CineCNN employs a convolutional neural network as an encoder-decoder model. Both methods are motivated by cinematographic principles, producing smooth and natural camera trajectories. Evaluation of basketball and stage performance datasets demonstrates superior performance over previous methods and baselines, both quantitatively and qualitatively. With a minor latency of half a second, CineConvex operates at approximately 250 frames per second (fps), while CineCNN achieves an impressive speed of 1000 fps, making them highly suitable for real-time applications. In the realm of video editing, we present Real Time GAZED, a real-time adaptation of the GAZED framework. It enables users to create professionally edited videos in real-time. Comparative evaluations against baseline methods, including the non-real-time GAZED, demonstrate that Real Time GAZED achieves similar editing results, ensuring high-quality video output. Furthermore, a user study confirms the aesthetic quality of the video edits produced by Real Time GAZED. With the advancements in real-time camera trajectory optimization and video editing presented, the demand for immediate and dynamic content creation in industries such as live broadcasting, sports coverage, news reporting, and social media content creation can be met more efficiently. The elimination of time-consuming post-production processes and the ability to deliver high-quality videos in today’s fast-paced digital landscape are the key advantages offered by these real-time approaches

Abstract

This thesis delves into the critical field of Domain Generalization (DG) in machine learning, where models are trained on multiple source distributions with the objective of generalizing to unseen tar- get distributions. We begin by dissecting various facets of DG, including distribution shifts, shortcut learning, representation learning, and data imbalances. This foundational investigation sets the stage for understanding the challenges associated with DG and the complexities that arise. A comprehensive literature review is conducted, highlighting existing challenges and contextualizing our contributions to the field. The review encompasses learning invariant features, parameter sharing techniques, meta-learning techniques, and data augmentation approaches. One of the key contributions of this thesis is the examination of the role low-dimensional representa- tions play in enhancing DG performance. We introduce a method to compute the implicit dimensionality of latent representations, exploring its correlation with performance in a domain generalization context. This essential finding motivated us to further investigate the effects of low-dimensional representations. Building on these insights, we present Cross-Domain Class-Contrastive Learning (CDCC), a tech- nique that learns sparse representations in the latent space, resulting in lower-dimensional represen- tations and improved domain generalization performance. CDCC establishes competitive results on various DG benchmarks, comparing favorably with numerous existing approaches in DomainBed. Venturing beyond traditional DG, we discuss a series of experiments conducted for domain general- ization in long-tailed settings, which are common in real-world applications. Additionally, we present supplementary experiments yielding intriguing findings. Our analysis reveals that the CDCC approach exhibits greater robustness in long-tailed distributions and that the order of performances across test do- mains remains unaffected by the order of training domains in the long-tailed setting. This section aims to inspire researchers to further probe the outcomes of these experiments and advance the understanding of domain generalization. In conclusion, this thesis offers a well-rounded exploration of DG by combining a comprehensive literature review, the discovery of the importance of low-dimensional representations in DG, the devel- opment of the CDCC method, and the meticulous analysis of long-tailed settings and other experimental findings.

Abstract

We address the problem of achieving fair and efficient allocation of resources in the era of rapid technological advancements, including Artificial Intelligence (AI) and the Internet of Things (IoT). The allocation of resources among autonomous agents is a crucial problem, and achieving fairness while ensuring efficiency is challenging. The objective is to determine the best way to divide resources among interested agents so that everyone is happy with their allocation, while ensuring fairness. We explore various fairness notions and relaxations that could apply to the problem of resource allocation. One of the main issues addressed in the thesis is the challenge of achieving fairness in the allocation of indivisible resources. We address several critical questions related to fair division, such as how to ensure fairness, how to generalize the notion of fairness, and what criteria to choose for different contexts. On top of it, fair division for goods and chores requires different approaches. We examine this issue in more detail and survey the existing approaches and provide solutions to overcome the challenges. We provide a detail survey on fairness notion and their approximate relaxations and evaluates their effectiveness in achieving fair and efficient allocations. In recent literature, researchers have delved into data-driven approaches in game theory and mechanism design to tackle the challenges of traditional approaches. Given the success of neural networks (NNs) in learning algorithms, and mechanisms, and solving mixedinteger programs, they offer a promising tool for achieving fair and efficient allocations of resources. Thus, we aim to use NNs to find an approximate fair allocation that maximizes social welfare in our pursuit of equitable and efficient resource distribution. Another criticaL issue addressed in the thesis is the presence of externalities, where the utility of an agent depends not only on their allocated resources but also on the resources allocated to other agents. Such scenarios are prevalent, especially in allocating critical resources such as hospital beds, ventilators, and vaccines during the COVID-19 pandemic. We evaluate the challenges of achieving fair and efficient allocations in the presence of externalities and propose potential solutions. Overall, in this thesis, we provide a comprehensive analysis of the challenges of achieving fair and efficient allocation of resources in the era of rapid technological advancements. The research proposes efficient algorithms and solutions to overcome the challenges and achieve approximately fair allocation in different contexts. Achieving fair and efficient resource allocation is crucial for various domains, including economics, politics, and social welfare, and the results of this could have significant implications in these domains.

Abstract

Global access to electricity has increased from 78.2% to 2000 to 90.5% in 2020, resulting in an increased electricity demand worldwide. Residential energy feedback is about providing personalized information on household energy use to consumers to encourage energy saving. Unlike commercial electricity consumption, which is managed by professionals, residential consumption is managed by the householders, who often lack insight into their energy usage. Quality feedback, including detailed energy consumption and tips, can lead to substantial household savings. There are several mediums for providing energy feedback, such as Short Message Service (SMS), postal letter, email, mobile app, and In-Home Display (IHD). Studies suggest that feedback through electronic media, like IHD, can save up to 20% of energy consumption. In this work, we aim to design mobile application interfaces that can maximize energy savings through effective feedback. The level of savings realized is dependent on the user’s preferences and understanding of the information presented. User preferences are subjective of their profile (e.g., age, occupation, income) and the cultural context (e.g., country). It is assumed that the possibility of energy reduction is high when the provided information matches the user’s display preferences. Despite the growing demand for quality energy feedback in India, we lack research that examines the Indian population perspective on energy feedback display user interface (UI) design. We conducted two questionnaire-based surveys, one to understand users’ preferences for feedback information and another to validate the designed mobile application interface screens. The surveys were conducted on two age groups, young and middle-aged adults. A Chi-Square Test of Independence was performed to assess the relationship between the user’s preference for feedback information and their age group. Participants identified total energy consumption, appliance level disaggregated information, energy-saving tips, goals, and historical consumption comparisons as the top five information types. In contrast, the normative comparison was the least preferred information. The follow-up design validations suggest that the interface should be customizable to accommodate the varying preferences of users. The current findings will help customize the energy feedback display UI design as per the Indian population.

Abstract

Protein allostery is a fundamental biological mechanism that plays a pivotal role in regulating various cellular processes. It allows proteins to change their shape and function in response to specific signals or ligands. In the context of nucleotide excision repair (NER), proteins involved in the repair process, such as the Rad4/XPC protein, undergo conformational changes when they bind to damaged DNA, which begin the lesion excision process by locating the lesion site, which is followed by the recruitment of other repair factors and facilitates the removal of damaged DNA segments. Essentially, protein allostery ensures that the repair machinery is only activated when and where it is needed, contributing to the precision and efficiency of DNA repair processes in cells. Molecular dynamics (MD) simulations enable the investigation of the conformational changes that facilitate complex, selective, and biologically significant processes involving proteins binding to a variety of substrates. Hence, the present work uses MD to study two processes that proteins participate in: (a) transcription modulation through mediator allostery and (b) locating UV-lesions present in DNA for their ultimate excision and repair. F-helices in CAP are able to ultimately recognise and bind to DNA for transcription when they undergo reorientation after cAMP, and a mediator has situated itself into the binding pockets of CAP. The present study uses a simulation-based approach to investigate the mechanism of cAMP-induced changes in the conformation and energetics of F-helices observed during the allosteric regulation of CAP by cAMP. The free energy profiles obtained by two-dimensional umbrella sampling of CAP and cAMPbound CAP provide a detailed picture of the elasticity modifications observed in the DNA-binding domain of CAP when cAMP is appropriately situated. Residue-wise interaction energy maps w.r.t. CAP residues under the different conformations of CAP, cAMP-bound CAP, and cAMP-bound DNAcomplexed CAP are created, which ultimately offer clues on the microscopic origin of the inter-subunit cooperativity and dimer stability of CAP. UV radiation-induced DNA damage has adverse effects on genome integrity and cellular function. The most prevalent DNA lesion is the cyclobutane pyrimidine dimer (CPD), implicated in a variety of genetic skin-related diseases and cancers in humans. Rad4/XPC is a damage-sensing protein that recognises and helps repair CPD lesions with high affinity. This binding efficiency of Rad4 depends on how efficiently the BHD2 and BHD3 domains have been associated with the CPD-containing lesion site of DNA. The present thesis investigates the mechanism, energetics, dynamics, and molecular basis for this Rad4-DNA association using CPD-containing perfectly matched DNA. This key molecular event that occurs in NER is studied using suitable reaction coordinates, and the resultant free energy surface when compared with the same of TTT/TTT mismatched DNA reveals that Rad4 has a higher tendency to stay in the associated conformation with CPD-containing DNA than TTT/TTT mismatched DNA, hence having a higher lesion-recognition efficiency on the former than the latter.

Abstract

Remote coordination between humans and robots has been of much interest over the past many years. In this thesis, we perform an empirical study regarding the comfort level of users in teleoperating a robotic manipulator to perform operations such as pick and place and stacking. We claim that such daily life operations while easy to perform by humans, are difficult to remotely operate using a manipulator due to their limited sensory perception. The problem is challenging because it requires optimum placement of cameras and an intuitive interface for the user to view and control the manipulator simultaneously. Hence, in our work, instead of limiting the control options, we give users the freedom to choose between controlling the manipulator using Cartesian Control and Joint Control, Joystick interface and also zoom in and out the various camera views for accurate visibility for pick and place and stacking tasks from a remote location. We validate our results by conducting the user trials on users with age between 21 and 63 from multiple countries. We observe that 71% of the users prefer using Cartesian space as the reference control, 57% feel the need for additional viewpoints for better visibility in first experiment which reduced to 29% in third experiment with different positioning of the same cameras, and more than 90% do not require the data from a distance sensor for guidance.

Abstract

Reinforcement Learning (RL) has witnessed remarkable advancements in both algorithms and engineering, enabling a wide range of exciting applications. Multi-agent Reinforcement Learning (MARL) in particular has made strides of progress enabling multiple learning entities to interact in effective manner. Few of the challenges that still remain are learning under sparse rewards, achieving social generalization by adapting to changing behaviours of other agents and reproducibility. This thesis tackles two important challenges in MARL: (1) learning in multi-agent sparse reward environments and (2) reproducibility with social generalization. In the first part, we address the issue of learning a reliable critic in multi-agent sparse reward scenarios. The exponential growth of the joint action space with the number of agents, coupled with reward sparsity and environmental noise, poses significant hurdles for accurate learning. To mitigate these challenges, we propose regularizing the critic with spectral normalization (SN). Our experiments demonstrate that the regularized critic exhibits improved robustness, enabling faster learning even in complex multi-agent scenarios. These findings highlight the importance of critic regularization for stable learning. In the second part, we introduce marl-jax, a powerful software package for MARL that focuses on training and evaluating social generalization of agents. Built on DeepMind’s JAX ecosystem and leveraging their RL framework, marl-jax supports cooperative and competitive environments with multiple agents acting simultaneously. It provides an intuitive command-line interface for training agent populations and evaluating their generalization capabilities. Researchers interested in exploring social generalization in MARL can leverage marl-jax as a reliable baseline. In conclusion, this thesis addresses two crucial challenges in RL: learning in multi-agent sparse reward scenarios and reproducibility for social generalization in MARL. By introducing spectral normalization as a regularization technique and providing the marl-jax software package, this research contributes to enhancing stability, robustness, social generalization and reproducibility in RL.

Abstract

Relational interpreters, interpreters written for programming languages as mathematical relations, have been studied for at least over a decade. However, while relational interpreters are mostly written in miniKanren, a relational language where programs are mathematical relations, the interpreted language tends to be non-relational. This dissertation presents metaKanren, a purely relational miniKanren-like language, and relational interpreter implemented as a deep embedding for metaKanren. We also construct a relational interpreter for a minimal relational language as a shallow embedding and point out the limitation of a shallow embedding, further emphasizing the need for a deep embedding. We show how one can perform program synthesis of miniKanren programs using our relational interpreter for metaKanren. We also show how to extend metaKanren and its relational interpreter to handle datatype constraints. Finally, we also show how metaKanren can be made fully metacircular, and precisely point out the problems in building a metacircular interpreter for miniKanren. This dissertation argues that it is feasible and useful to build a metacircular relational interpreter for miniKanren