Showing 1–50 of 121 results for author: Chakrabarti, A

Enhancing Electrocardiogram Signal Analysis Using NLP-Inspired Techniques: A Novel Approach with Embedding and Self-Attention

Authors: Prapti Ganguly, Wazib Ansar, Amlan Chakrabarti

Abstract: A language is made up of an infinite/finite number of sentences, which in turn is composed of a number of words. The Electrocardiogram (ECG) is the most popular noninvasive medical tool for studying heart function and diagnosing various irregular cardiac rhythms. Intuitive inspection of the ECG reveals a marked similarity between ECG signals and the spoken language. As a result, the ECG signal may… ▽ More A language is made up of an infinite/finite number of sentences, which in turn is composed of a number of words. The Electrocardiogram (ECG) is the most popular noninvasive medical tool for studying heart function and diagnosing various irregular cardiac rhythms. Intuitive inspection of the ECG reveals a marked similarity between ECG signals and the spoken language. As a result, the ECG signal may be thought of as a series of heartbeats (similar to sentences in a spoken language), with each heartbeat consisting of a collection of waves (similar to words in a sentence) with varying morphologies. Just as natural language processing (NLP) is used to help computers comprehend and interpret human natural language, it is conceivable to create NLP-inspired algorithms to help computers comprehend the electrocardiogram data more efficiently. In this study, we propose a novel ECG analysis technique, based on embedding and self attention, to capture the spatial as well as the temporal dependencies of the ECG data. To generate the embedding, an encoder-decoder network was proposed to capture the temporal dependencies of the ECG signal and perform data compression. The compressed and encoded data was fed to the embedding layer as its weights. Finally, the proposed CNN-LSTM-Self Attention classifier works on the embedding layer and classifies the signal as normal or anomalous. The approach was tested using the PTB-xl dataset, which is severely imbalanced. Our emphasis was to appropriately recognise the disease classes present in minority numbers, in order to limit the detection of False Negative cases. An accuracy of 91% was achieved with a good F1-score for all the disease classes. Additionally, the the size of the model was reduced by 34% due to compression, making it suitable for deployment in real time applications △ Less

Submitted 15 July, 2024; originally announced July 2024.

A Study on Effect of Reference Knowledge Choice in Generating Technical Content Relevant to SAPPhIRE Model Using Large Language Model

Authors: Kausik Bhattacharya, Anubhab Majumder, Amaresh Chakrabarti

Abstract: Representation of systems using the SAPPhIRE model of causality can be an inspirational stimulus in design. However, creating a SAPPhIRE model of a technical or a natural system requires sourcing technical knowledge from multiple technical documents regarding how the system works. This research investigates how to generate technical content accurately relevant to the SAPPhIRE model of causality us… ▽ More Representation of systems using the SAPPhIRE model of causality can be an inspirational stimulus in design. However, creating a SAPPhIRE model of a technical or a natural system requires sourcing technical knowledge from multiple technical documents regarding how the system works. This research investigates how to generate technical content accurately relevant to the SAPPhIRE model of causality using a Large Language Model, also called LLM. This paper, which is the first part of the two-part research, presents a method for hallucination suppression using Retrieval Augmented Generating with LLM to generate technical content supported by the scientific information relevant to a SAPPhIRE con-struct. The result from this research shows that the selection of reference knowledge used in providing context to the LLM for generating the technical content is very important. The outcome of this research is used to build a software support tool to generate the SAPPhIRE model of a given technical system. △ Less

Submitted 29 June, 2024; originally announced July 2024.

Development and Evaluation of a Retrieval-Augmented Generation Tool for Creating SAPPhIRE Models of Artificial Systems

Authors: Anubhab Majumder, Kausik Bhattacharya, Amaresh Chakrabarti

Abstract: Representing systems using the SAPPhIRE causality model is found useful in supporting design-by-analogy. However, creating a SAPPhIRE model of artificial or biological systems is an effort-intensive process that requires human experts to source technical knowledge from multiple technical documents regarding how the system works. This research investigates how to leverage Large Language Models (LLM… ▽ More Representing systems using the SAPPhIRE causality model is found useful in supporting design-by-analogy. However, creating a SAPPhIRE model of artificial or biological systems is an effort-intensive process that requires human experts to source technical knowledge from multiple technical documents regarding how the system works. This research investigates how to leverage Large Language Models (LLMs) in creating structured descriptions of systems using the SAPPhIRE model of causality. This paper, the second part of the two-part research, presents a new Retrieval-Augmented Generation (RAG) tool for generating information related to SAPPhIRE constructs of artificial systems and reports the results from a preliminary evaluation of the tool's success - focusing on the factual accuracy and reliability of outcomes. △ Less

Submitted 27 June, 2024; originally announced June 2024.

A Survey on Transformers in NLP with Focus on Efficiency

Authors: Wazib Ansar, Saptarsi Goswami, Amlan Chakrabarti

Abstract: The advent of transformers with attention mechanisms and associated pre-trained models have revolutionized the field of Natural Language Processing (NLP). However, such models are resource-intensive due to highly complex architecture. This limits their application to resource-constrained environments. While choosing an appropriate NLP model, a major trade-off exists over choosing accuracy over eff… ▽ More The advent of transformers with attention mechanisms and associated pre-trained models have revolutionized the field of Natural Language Processing (NLP). However, such models are resource-intensive due to highly complex architecture. This limits their application to resource-constrained environments. While choosing an appropriate NLP model, a major trade-off exists over choosing accuracy over efficiency and vice versa. This paper presents a commentary on the evolution of NLP and its applications with emphasis on their accuracy as-well-as efficiency. Following this, a survey of research contributions towards enhancing the efficiency of transformer-based models at various stages of model development along with hardware considerations has been conducted. The goal of this survey is to determine how current NLP techniques contribute towards a sustainable society and to establish a foundation for future research. △ Less

Submitted 15 May, 2024; originally announced June 2024.

TexIm FAST: Text-to-Image Representation for Semantic Similarity Evaluation using Transformers

Authors: Wazib Ansar, Saptarsi Goswami, Amlan Chakrabarti

Abstract: One of the principal objectives of Natural Language Processing (NLP) is to generate meaningful representations from text. Improving the informativeness of the representations has led to a tremendous rise in the dimensionality and the memory footprint. It leads to a cascading effect amplifying the complexity of the downstream model by increasing its parameters. The available techniques cannot be ap… ▽ More One of the principal objectives of Natural Language Processing (NLP) is to generate meaningful representations from text. Improving the informativeness of the representations has led to a tremendous rise in the dimensionality and the memory footprint. It leads to a cascading effect amplifying the complexity of the downstream model by increasing its parameters. The available techniques cannot be applied to cross-modal applications such as text-to-image. To ameliorate these issues, a novel Text-to-Image methodology for generating fixed-length representations through a self-supervised Variational Auto-Encoder (VAE) for semantic evaluation applying transformers (TexIm FAST) has been proposed in this paper. The pictorial representations allow oblivious inference while retaining the linguistic intricacies, and are potent in cross-modal applications. TexIm FAST deals with variable-length sequences and generates fixed-length representations with over 75% reduced memory footprint. It enhances the efficiency of the models for downstream tasks by reducing its parameters. The efficacy of TexIm FAST has been extensively analyzed for the task of Semantic Textual Similarity (STS) upon the MSRPC, CNN/ Daily Mail, and XSum data-sets. The results demonstrate 6% improvement in accuracy compared to the baseline and showcase its exceptional ability to compare disparate length sequences such as a text with its summary. △ Less

Submitted 6 June, 2024; originally announced June 2024.

Comments: 19 pages, 33 figures

Lumbar Spine Tumor Segmentation and Localization in T2 MRI Images Using AI

Authors: Rikathi Pal, Sudeshna Mondal, Aditi Gupta, Priya Saha, Somoballi Ghoshal, Amlan Chakrabarti, Susmita Sur-Kolay

Abstract: In medical imaging, segmentation and localization of spinal tumors in three-dimensional (3D) space pose significant computational challenges, primarily stemming from limited data availability. In response, this study introduces a novel data augmentation technique, aimed at automating spine tumor segmentation and localization through AI approaches. Leveraging a fusion of fuzzy c-means clustering an… ▽ More In medical imaging, segmentation and localization of spinal tumors in three-dimensional (3D) space pose significant computational challenges, primarily stemming from limited data availability. In response, this study introduces a novel data augmentation technique, aimed at automating spine tumor segmentation and localization through AI approaches. Leveraging a fusion of fuzzy c-means clustering and Random Forest algorithms, the proposed method achieves successful spine tumor segmentation based on predefined masks initially delineated by domain experts in medical imaging. Subsequently, a Convolutional Neural Network (CNN) architecture is employed for tumor classification. Moreover, 3D vertebral segmentation and labeling techniques are used to help pinpoint the exact location of the tumors in the lumbar spine. Results indicate a remarkable performance, with 99% accuracy for tumor segmentation, 98% accuracy for tumor classification, and 99% accuracy for tumor localization achieved with the proposed approach. These metrics surpass the efficacy of existing state-of-the-art techniques, as evidenced by superior Dice Score, Class Accuracy, and Intersection over Union (IOU) on class accuracy metrics. This innovative methodology holds promise for enhancing the diagnostic capabilities in detecting and characterizing spinal tumors, thereby facilitating more effective clinical decision-making. △ Less

Submitted 7 May, 2024; originally announced May 2024.

Comments: 9 pages, 12 figures

Panoptic Segmentation and Labelling of Lumbar Spine Vertebrae using Modified Attention Unet

Authors: Rikathi Pal, Priya Saha, Somoballi Ghoshal, Amlan Chakrabarti, Susmita Sur-Kolay

Abstract: Segmentation and labeling of vertebrae in MRI images of the spine are critical for the diagnosis of illnesses and abnormalities. These steps are indispensable as MRI technology provides detailed information about the tissue structure of the spine. Both supervised and unsupervised segmentation methods exist, yet acquiring sufficient data remains challenging for achieving high accuracy. In this stud… ▽ More Segmentation and labeling of vertebrae in MRI images of the spine are critical for the diagnosis of illnesses and abnormalities. These steps are indispensable as MRI technology provides detailed information about the tissue structure of the spine. Both supervised and unsupervised segmentation methods exist, yet acquiring sufficient data remains challenging for achieving high accuracy. In this study, we propose an enhancing approach based on modified attention U-Net architecture for panoptic segmentation of 3D sliced MRI data of the lumbar spine. Our method achieves an impressive accuracy of 99.5\% by incorporating novel masking logic, thus significantly advancing the state-of-the-art in vertebral segmentation and labeling. This contributes to more precise and reliable diagnosis and treatment planning. △ Less

Submitted 28 April, 2024; originally announced April 2024.

Comments: 9 pages, 10 figures

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams

Authors: Amit Chakrabarti, Andrew McGregor, Anthony Wirth

Abstract: The maximum coverage problem is to select $k$ sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider $(1-1/e-ε)$-approximation algorithms for this NP-hard problem in three standard data stream models. 1. {\em Dynamic Model.} The stream consists of a sequence of sets being inserted and deleted. Our multi-pass algorithm uses… ▽ More The maximum coverage problem is to select $k$ sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider $(1-1/e-ε)$-approximation algorithms for this NP-hard problem in three standard data stream models. 1. {\em Dynamic Model.} The stream consists of a sequence of sets being inserted and deleted. Our multi-pass algorithm uses $ε^{-2} k \cdot \text{polylog}(n,m)$ space. The best previous result (Assadi and Khanna, SODA 2018) used $(n +ε^{-4} k) \text{polylog}(n,m)$ space. While both algorithms use $O(ε^{-1} \log n)$ passes, our analysis shows that when $ε$ is a constant, it is possible to reduce the number of passes by a $1/\log \log n$ factor without incurring additional space. 2. {\em Random Order Model.} In this model, there are no deletions and the sets forming the instance are uniformly randomly permuted to form the input stream. We show that a single pass and $k \text{polylog}(n,m)$ space suffices for arbitrary small constant $ε$. The best previous result, by Warneke et al.~(ESA 2023), used $k^2 \text{polylog}(n,m)$ space. 3. {\em Insert-Only Model.} Lastly, our results, along with numerous previous results, use a sub-sampling technique introduced by McGregor and Vu (ICDT 2017) to sparsify the input instance. We explain how this technique and others used in the paper can be implemented such that the amortized update time of our algorithm is polylogarithmic. This also implies an improvement of the state-of-the-art insert only algorithms in terms of the update time: $\text{polylog}(m,n)$ update time suffices whereas the best previous result by Jaud et al.~(SEA 2023) required update time that was linear in $k$. △ Less

Submitted 20 March, 2024; originally announced March 2024.

ACM Class: F.2.2

SpacTor-T5: Pre-training T5 Models with Span Corruption and Replaced Token Detection

Authors: Ke Ye, Heinrich Jiang, Afshin Rostamizadeh, Ayan Chakrabarti, Giulia DeSalvo, Jean-François Kagy, Lazaros Karydas, Gui Citovsky, Sanjiv Kumar

Abstract: Pre-training large language models is known to be extremely resource intensive and often times inefficient, under-utilizing the information encapsulated in the training text sequences. In this paper, we present SpacTor, a new training procedure consisting of (1) a hybrid objective combining span corruption (SC) and token replacement detection (RTD), and (2) a two-stage curriculum that optimizes th… ▽ More Pre-training large language models is known to be extremely resource intensive and often times inefficient, under-utilizing the information encapsulated in the training text sequences. In this paper, we present SpacTor, a new training procedure consisting of (1) a hybrid objective combining span corruption (SC) and token replacement detection (RTD), and (2) a two-stage curriculum that optimizes the hybrid objective over the initial $τ$ iterations, then transitions to standard SC loss. We show empirically that the effectiveness of the hybrid objective is tied to the two-stage pre-training schedule, and provide extensive analysis on why this is the case. In our experiments with encoder-decoder architectures (T5) on a variety of NLP tasks, SpacTor-T5 yields the same downstream performance as standard SC pre-training, while enabling a 50% reduction in pre-training iterations and 40% reduction in total FLOPs. Alternatively, given the same amount of computing budget, we find that SpacTor results in significantly improved downstream benchmark performance. △ Less

Submitted 23 January, 2024; originally announced January 2024.

Comments: 9+13 pages, 5 figures

Rethinking FID: Towards a Better Evaluation Metric for Image Generation

Authors: Sadeep Jayasumana, Srikumar Ramalingam, Andreas Veit, Daniel Glasner, Ayan Chakrabarti, Sanjiv Kumar

Abstract: As with many machine learning problems, the progress of image generation methods hinges on good evaluation metrics. One of the most popular is the Frechet Inception Distance (FID). FID estimates the distance between a distribution of Inception-v3 features of real images, and those of images generated by the algorithm. We highlight important drawbacks of FID: Inception's poor representation of the… ▽ More As with many machine learning problems, the progress of image generation methods hinges on good evaluation metrics. One of the most popular is the Frechet Inception Distance (FID). FID estimates the distance between a distribution of Inception-v3 features of real images, and those of images generated by the algorithm. We highlight important drawbacks of FID: Inception's poor representation of the rich and varied content generated by modern text-to-image models, incorrect normality assumptions, and poor sample complexity. We call for a reevaluation of FID's use as the primary quality metric for generated images. We empirically demonstrate that FID contradicts human raters, it does not reflect gradual improvement of iterative text-to-image models, it does not capture distortion levels, and that it produces inconsistent results when varying the sample size. We also propose an alternative new metric, CMMD, based on richer CLIP embeddings and the maximum mean discrepancy distance with the Gaussian RBF kernel. It is an unbiased estimator that does not make any assumptions on the probability distribution of the embeddings and is sample efficient. Through extensive experiments and analysis, we demonstrate that FID-based evaluations of text-to-image models may be unreliable, and that CMMD offers a more robust and reliable assessment of image quality. △ Less

Submitted 25 January, 2024; v1 submitted 30 November, 2023; originally announced January 2024.

Comments: Code is available at: https://github.com/google-research/google-research/tree/master/cmmd

Finding missing items requires strong forms of randomness

Authors: Amit Chakrabarti, Manuel Stoeckl

Abstract: Adversarially robust streaming algorithms are required to process a stream of elements and produce correct outputs, even when each stream element can be chosen as a function of earlier algorithm outputs. As with classic streaming algorithms, which must only be correct for the worst-case fixed stream, adversarially robust algorithms with access to randomness can use significantly less space than de… ▽ More Adversarially robust streaming algorithms are required to process a stream of elements and produce correct outputs, even when each stream element can be chosen as a function of earlier algorithm outputs. As with classic streaming algorithms, which must only be correct for the worst-case fixed stream, adversarially robust algorithms with access to randomness can use significantly less space than deterministic algorithms. We prove that for the Missing Item Finding problem in streaming, the space complexity also significantly depends on how adversarially robust algorithms are permitted to use randomness. (In contrast, the space complexity of classic streaming algorithms does not depend as strongly on the way randomness is used.) For Missing Item Finding on streams of length $\ell$ with elements in $\{1,\ldots,n\}$, and $\le 1/\text{poly}(\ell)$ error, we show that when $\ell = O(2^{\sqrt{\log n}})$, "random seed" adversarially robust algorithms, which only use randomness at initialization, require $\ell^{Ω(1)}$ bits of space, while "random tape" adversarially robust algorithms, which may make random decisions at any time, may use $O(\text{polylog}(\ell))$ space. When $\ell$ is between $n^{Ω(1)}$ and $O(\sqrt{n})$, "random tape" adversarially robust algorithms need $\ell^{Ω(1)}$ space, while "random oracle" adversarially robust algorithms, which can read from a long random string for free, may use $O(\text{polylog}(\ell))$ space. The space lower bound for the "random seed" case follows, by a reduction given in prior work, from a lower bound for pseudo-deterministic streaming algorithms given in this paper. △ Less

Submitted 2 July, 2024; v1 submitted 5 October, 2023; originally announced October 2023.

Comments: 46 pages, 3 figures; since v1, rewrote Sec 2, simplified proofs in Sec 4, clarified Sec 6, changed title from "When a random tape is not enough: lower bounds for a problem in adversarially robust streaming", and made many minor improvements

FragQC: An Efficient Quantum Error Reduction Technique using Quantum Circuit Fragmentation

Authors: Saikat Basu, Arnav Das, Amit Saha, Amlan Chakrabarti, Susmita Sur-Kolay

Abstract: Quantum computers must meet extremely stringent qualitative and quantitative requirements on their qubits in order to solve real-life problems. Quantum circuit fragmentation techniques divide a large quantum circuit into a number of sub-circuits that can be executed on the smaller noisy quantum hardware available. However, the process of quantum circuit fragmentation involves finding an ideal cut… ▽ More Quantum computers must meet extremely stringent qualitative and quantitative requirements on their qubits in order to solve real-life problems. Quantum circuit fragmentation techniques divide a large quantum circuit into a number of sub-circuits that can be executed on the smaller noisy quantum hardware available. However, the process of quantum circuit fragmentation involves finding an ideal cut that has exponential time complexity, and also classical post-processing required to reconstruct the output. In this paper, we represent a quantum circuit using a weighted graph and propose a novel classical graph partitioning algorithm for selecting an efficient fragmentation that reduces the entanglement between the sub-circuits along with balancing the estimated error in each sub-circuit. We also demonstrate a comparative study over different classical and quantum approaches of graph partitioning for finding such a cut. We present {\it FragQC}, a software tool that cuts a quantum circuit into sub-circuits when its error probability exceeds a certain threshold. With this proposed approach, we achieve an increase of fidelity by 14.83\% compared to direct execution without cutting the circuit, and 8.45\% over the state-of-the-art ILP-based method, for the benchmark circuits. △ Less

Submitted 30 September, 2023; originally announced October 2023.

Comments: 30 pages, 9 figures

Journal ref: Journal of Systems and Software 2024

MarkovGen: Structured Prediction for Efficient Text-to-Image Generation

Authors: Sadeep Jayasumana, Daniel Glasner, Srikumar Ramalingam, Andreas Veit, Ayan Chakrabarti, Sanjiv Kumar

Abstract: Modern text-to-image generation models produce high-quality images that are both photorealistic and faithful to the text prompts. However, this quality comes at significant computational cost: nearly all of these models are iterative and require running sampling multiple times with large models. This iterative process is needed to ensure that different regions of the image are not only aligned wit… ▽ More Modern text-to-image generation models produce high-quality images that are both photorealistic and faithful to the text prompts. However, this quality comes at significant computational cost: nearly all of these models are iterative and require running sampling multiple times with large models. This iterative process is needed to ensure that different regions of the image are not only aligned with the text prompt, but also compatible with each other. In this work, we propose a light-weight approach to achieving this compatibility between different regions of an image, using a Markov Random Field (MRF) model. We demonstrate the effectiveness of this method on top of the latent token-based Muse text-to-image model. The MRF richly encodes the compatibility among image tokens at different spatial locations to improve quality and significantly reduce the required number of Muse sampling steps. Inference with the MRF is significantly cheaper, and its parameters can be quickly learned through back-propagation by modeling MRF inference as a differentiable neural-network layer. Our full model, MarkovGen, uses this proposed MRF model to both speed up Muse by 1.5X and produce higher quality images by decreasing undesirable image artifacts. △ Less

Submitted 15 December, 2023; v1 submitted 14 August, 2023; originally announced August 2023.

SoccerKDNet: A Knowledge Distillation Framework for Action Recognition in Soccer Videos

Authors: Sarosij Bose, Saikat Sarkar, Amlan Chakrabarti

Abstract: Classifying player actions from soccer videos is a challenging problem, which has become increasingly important in sports analytics over the years. Most state-of-the-art methods employ highly complex offline networks, which makes it difficult to deploy such models in resource constrained scenarios. Here, in this paper we propose a novel end-to-end knowledge distillation based transfer learning net… ▽ More Classifying player actions from soccer videos is a challenging problem, which has become increasingly important in sports analytics over the years. Most state-of-the-art methods employ highly complex offline networks, which makes it difficult to deploy such models in resource constrained scenarios. Here, in this paper we propose a novel end-to-end knowledge distillation based transfer learning network pre-trained on the Kinetics400 dataset and then perform extensive analysis on the learned framework by introducing a unique loss parameterization. We also introduce a new dataset named SoccerDB1 containing 448 videos and consisting of 4 diverse classes each of players playing soccer. Furthermore, we introduce an unique loss parameter that help us linearly weigh the extent to which the predictions of each network are utilized. Finally, we also perform a thorough performance study using various changed hyperparameters. We also benchmark the first classification results on the new SoccerDB1 dataset obtaining 67.20% validation accuracy. Apart from outperforming prior arts significantly, our model also generalizes to new datasets easily. The dataset has been made publicly available at: https://bit.ly/soccerdb1 △ Less

Submitted 22 July, 2023; v1 submitted 15 July, 2023; originally announced July 2023.

Comments: Accepted to 10th Springer PReMI 2023

Substance or Style: What Does Your Image Embedding Know?

Authors: Cyrus Rashtchian, Charles Herrmann, Chun-Sung Ferng, Ayan Chakrabarti, Dilip Krishnan, Deqing Sun, Da-Cheng Juan, Andrew Tomkins

Abstract: Probes are small networks that predict properties of underlying data from embeddings, and they provide a targeted, effective way to illuminate the information contained in embeddings. While analysis through the use of probes has become standard in NLP, there has been much less exploration in vision. Image foundation models have primarily been evaluated for semantic content. Better understanding th… ▽ More Probes are small networks that predict properties of underlying data from embeddings, and they provide a targeted, effective way to illuminate the information contained in embeddings. While analysis through the use of probes has become standard in NLP, there has been much less exploration in vision. Image foundation models have primarily been evaluated for semantic content. Better understanding the non-semantic information in popular embeddings (e.g., MAE, SimCLR, or CLIP) will shed new light both on the training algorithms and on the uses for these foundation models. We design a systematic transformation prediction task and measure the visual content of embeddings along many axes, including image style, quality, and a range of natural and artificial transformations. Surprisingly, six embeddings (including SimCLR) encode enough non-semantic information to identify dozens of transformations. We also consider a generalization task, where we group similar transformations and hold out several for testing. We find that image-text models (CLIP and ALIGN) are better at recognizing new examples of style transfer than masking-based models (CAN and MAE). Overall, our results suggest that the choice of pre-training algorithm impacts the types of information in the embedding, and certain models are better than others for non-semantic downstream tasks. △ Less

Submitted 10 July, 2023; originally announced July 2023.

Comments: 27 pages, 9 figures

Fast 3D Volumetric Image Reconstruction from 2D MRI Slices by Parallel Processing

Authors: Somoballi Ghoshal, Shremoyee Goswami, Amlan Chakrabarti, Susmita Sur-Kolay

Abstract: Magnetic Resonance Imaging (MRI) is a technology for non-invasive imaging of anatomical features in detail. It can help in functional analysis of organs of a specimen but it is very costly. In this work, methods for (i) virtual three-dimensional (3D) reconstruction from a single sequence of two-dimensional (2D) slices of MR images of a human spine and brain along a single axis, and (ii) generation… ▽ More Magnetic Resonance Imaging (MRI) is a technology for non-invasive imaging of anatomical features in detail. It can help in functional analysis of organs of a specimen but it is very costly. In this work, methods for (i) virtual three-dimensional (3D) reconstruction from a single sequence of two-dimensional (2D) slices of MR images of a human spine and brain along a single axis, and (ii) generation of missing inter-slice data are proposed. Our approach helps in preserving the edges, shape, size, as well as the internal tissue structures of the object being captured. The sequence of original 2D slices along a single axis is divided into smaller equal sub-parts which are then reconstructed using edge preserved kriging interpolation to predict the missing slice information. In order to speed up the process of interpolation, we have used multiprocessing by carrying out the initial interpolation on parallel cores. From the 3D matrix thus formed, shearlet transform is applied to estimate the edges considering the 2D blocks along the $Z$ axis, and to minimize the blurring effect using a proposed mean-median logic. Finally, for visualization, the sub-matrices are merged into a final 3D matrix. Next, the newly formed 3D matrix is split up into voxels and marching cubes method is applied to get the approximate 3D image for viewing. To the best of our knowledge it is a first of its kind approach based on kriging interpolation and multiprocessing for 3D reconstruction from 2D slices, and approximately 98.89\% accuracy is achieved with respect to similarity metrics for image comparison. The time required for reconstruction has also been reduced by approximately 70\% with multiprocessing even for a large input data set compared to that with single core processing. △ Less

Submitted 16 March, 2023; originally announced March 2023.

Comments: 19 pages, figure 14

Benchmarking Robustness to Adversarial Image Obfuscations

Authors: Florian Stimberg, Ayan Chakrabarti, Chun-Ta Lu, Hussein Hazimeh, Otilia Stretcu, Wei Qiao, Yintao Liu, Merve Kaya, Cyrus Rashtchian, Ariel Fuxman, Mehmet Tek, Sven Gowal

Abstract: Automated content filtering and moderation is an important tool that allows online platforms to build striving user communities that facilitate cooperation and prevent abuse. Unfortunately, resourceful actors try to bypass automated filters in a bid to post content that violate platform policies and codes of conduct. To reach this goal, these malicious actors may obfuscate policy violating images… ▽ More Automated content filtering and moderation is an important tool that allows online platforms to build striving user communities that facilitate cooperation and prevent abuse. Unfortunately, resourceful actors try to bypass automated filters in a bid to post content that violate platform policies and codes of conduct. To reach this goal, these malicious actors may obfuscate policy violating images (e.g. overlay harmful images by carefully selected benign images or visual patterns) to prevent machine learning models from reaching the correct decision. In this paper, we invite researchers to tackle this specific issue and present a new image benchmark. This benchmark, based on ImageNet, simulates the type of obfuscations created by malicious actors. It goes beyond ImageNet-$\textrm{C}$ and ImageNet-$\bar{\textrm{C}}$ by proposing general, drastic, adversarial modifications that preserve the original content intent. It aims to tackle a more common adversarial threat than the one considered by $\ell_p$-norm bounded adversaries. We evaluate 33 pretrained models on the benchmark and train models with different augmentations, architectures and training methods on subsets of the obfuscations to measure generalization. We hope this benchmark will encourage researchers to test their models and methods and try to find new approaches that are more robust to these obfuscations. △ Less

Submitted 29 November, 2023; v1 submitted 30 January, 2023; originally announced January 2023.

ACM Class: I.2.10; I.4.0

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms

Authors: Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

Abstract: In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially randomized, raising natural questions about how important a role randomization plays in streaming graph coloring. A couple of very recent works have made progress on this question: they prove that deterministic or even a… ▽ More In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially randomized, raising natural questions about how important a role randomization plays in streaming graph coloring. A couple of very recent works have made progress on this question: they prove that deterministic or even adversarially robust coloring algorithms (that work on streams whose updates may depend on the algorithm's past outputs) are considerably weaker than standard randomized ones. However, there is still a significant gap between the upper and lower bounds for the number of colors needed (as a function of the maximum degree $Δ$) for robust coloring and multipass deterministic coloring. We contribute to this line of work by proving the following results. In the deterministic semi-streaming (i.e., $O(n \cdot \text{polylog } n)$ space) regime, we present an algorithm that achieves a combinatorially optimal $(Δ+1)$-coloring using $O(\logΔ \log\logΔ)$ passes. This improves upon the prior $O(Δ)$-coloring algorithm of Assadi, Chen, and Sun (STOC 2022) at the cost of only an $O(\log\logΔ)$ factor in the number of passes. In the adversarially robust semi-streaming regime, we design an $O(Δ^{5/2})$-coloring algorithm that improves upon the previously best $O(Δ^{3})$-coloring algorithm of Chakrabarti, Ghosh, and Stoeckl (ITCS 2022). Further, we obtain a smooth colors/space tradeoff that improves upon another algorithm of the said work: whereas their algorithm uses $O(Δ^2)$ colors and $O(nΔ^{1/2})$ space, ours, in particular, achieves (i)~$O(Δ^2)$ colors in $O(nΔ^{1/3})$ space, and (ii)~$O(Δ^{7/4})$ colors in $O(nΔ^{1/2})$ space. △ Less

Submitted 20 December, 2022; originally announced December 2022.

Comments: 29 pages

Robust Quantum Circuit for Clique Problem with Intermediate Qudits

Authors: Arpita Sanyal, Amit Saha, Banani Saha, Amlan Chakrabarti

Abstract: Clique problem has a wide range of applications due to its pattern matching ability. There are various formulation of clique problem like $k$-clique problem, maximum clique problem, etc. The $k$-Clique problem, determines whether an arbitrary network has a clique or not whereas maximum clique problem finds the largest clique in a graph. It is already exhibited in the literature that the $k$-clique… ▽ More Clique problem has a wide range of applications due to its pattern matching ability. There are various formulation of clique problem like $k$-clique problem, maximum clique problem, etc. The $k$-Clique problem, determines whether an arbitrary network has a clique or not whereas maximum clique problem finds the largest clique in a graph. It is already exhibited in the literature that the $k$-clique or maximum clique problem (NP-problem) can be solved in an asymptotically faster manner by using quantum algorithms as compared to the conventional computing. Quantum computing with higher dimensions is gaining popularity due to its large storage capacity and computation power. In this article, we have shown an improved quantum circuit implementation for the $k$-clique problem and maximum clique problem (MCP) with the help of higher-dimensional intermediate temporary qudits for the first time to the best of our knowledge. The cost of state-of-the-art quantum circuit for $k$-clique problem is colossal due to a huge number of $n$-qubit Toffoli gates. We have exhibited an improved cost and depth over the circuit by applying a generalized $n$-qubit Toffoli gate decomposition with intermediate ququarts (4-dimensional qudits). △ Less

Submitted 15 November, 2022; originally announced November 2022.

Comments: 19 pages, 22 figures

Journal ref: Nano Communication Networks Volume 37 (2023)

Adaptive Edge Offloading for Image Classification Under Rate Limit

Authors: Jiaming Qiu, Ruiqi Wang, Ayan Chakrabarti, Roch Guerin, Chenyang Lu

Abstract: This paper considers a setting where embedded devices are used to acquire and classify images. Because of limited computing capacity, embedded devices rely on a parsimonious classification model with uneven accuracy. When local classification is deemed inaccurate, devices can decide to offload the image to an edge server with a more accurate but resource-intensive model. Resource constraints, e.g.… ▽ More This paper considers a setting where embedded devices are used to acquire and classify images. Because of limited computing capacity, embedded devices rely on a parsimonious classification model with uneven accuracy. When local classification is deemed inaccurate, devices can decide to offload the image to an edge server with a more accurate but resource-intensive model. Resource constraints, e.g., network bandwidth, however, require regulating such transmissions to avoid congestion and high latency. The paper investigates this offloading problem when transmissions regulation is through a token bucket, a mechanism commonly used for such purposes. The goal is to devise a lightweight, online offloading policy that optimizes an application-specific metric (e.g., classification accuracy) under the constraints of the token bucket. The paper develops a policy based on a Deep Q-Network (DQN), and demonstrates both its efficacy and the feasibility of its deployment on embedded devices. Of note is the fact that the policy can handle complex input patterns, including correlation in image arrivals and classification accuracy. The evaluation is carried out by performing image classification over a local testbed using synthetic traces generated from the ImageNet image classification benchmark. Implementation of this work is available at https://github.com/qiujiaming315/edgeml-dqn. △ Less

Submitted 31 July, 2022; originally announced August 2022.

Comments: 13 pages, 12 figures, to appear at the Proceedings of the 2022 International Conference on Embedded Software, October 07-14, 2022, Shanghai, China

Optimal Codeword Construction for DNA-based Finite Automata

Authors: Anupam Chattopadhyay, Arnab Chakrabarti

Abstract: Biomolecular computation has emerged as an important area of computer science research due to its high information density, immense parallelism opportunity along with potential applications in cryptography, genetic engineering and bioinformatics. Computational frameworks using DNA molecules have been proposed in the literature to accomplish varied tasks such as simulating logical operations, perfo… ▽ More Biomolecular computation has emerged as an important area of computer science research due to its high information density, immense parallelism opportunity along with potential applications in cryptography, genetic engineering and bioinformatics. Computational frameworks using DNA molecules have been proposed in the literature to accomplish varied tasks such as simulating logical operations, performing matrix multiplication, and encoding instances of NP-hard problems. In one of the key applications, several studies have proposed construction of finite automata using DNA hybridisation and ligation. The state and symbol encoding of these finite automata are done manually. In this manuscript, we study the codeword construction problem for this approach. We derive exact theoretical bounds on the number of symbols and states in the finite automata and also obtain the complete set of symbols in a specific case. For automatic encoding, two different solutions, based on a heuristic and on Integer Linear Programming (ILP), are proposed. Furthermore, we propose an early simulation-based validation of laboratory experiments. Our proposed flow accepts a finite automaton, automatically encodes the symbols for the actual experiments and executes the simulation step-by-step. △ Less

Submitted 4 June, 2022; originally announced June 2022.

Efficient hybrid topology optimization using GPU and homogenization based multigrid approach

Authors: Arya Prakash Padhi, Souvik Chakraborty, Anupam Chakrabarti, Rajib Chowdhury

Abstract: We propose a new hybrid topology optimization algorithm based on multigrid approach that combines the parallelization strategy of CPU using OpenMP and heavily multithreading capabilities of modern Graphics Processing Units (GPU). In addition to that significant computational efficiency in memory requirement has been achieved using homogenization strategy. The algorithm has been integrated with ver… ▽ More We propose a new hybrid topology optimization algorithm based on multigrid approach that combines the parallelization strategy of CPU using OpenMP and heavily multithreading capabilities of modern Graphics Processing Units (GPU). In addition to that significant computational efficiency in memory requirement has been achieved using homogenization strategy. The algorithm has been integrated with versitile computing platform of MATLAB for ease of use and customization. The bottlenecking repetitive solution of the state equation has been solved using an optimized geometric multigrid approach along with CUDA parallelization enabling an order of magnitude faster in computational time than current state of the art implementations. On-the-fly computation of auxiliary matrices in the multigrid scheme and modification in interpolation schemes using homogenization strategy removes memory limitation of GPUs. Memory hierarchy of GPU has also been exploited for further optimized implementations. All these enable solution of structures involving hundred millions of three dimensional brick elements to be accomplished in a standard desktop computer or a workstation. Performance of the proposed algorithm is illustrated using several examples including design dependent loads and multimaterial.Results obtained indicate the excellent performance and scalability of the proposed approach. △ Less

Submitted 27 January, 2022; originally announced January 2022.

Comments: 25 pages

Counting Simplices in Hypergraph Streams

Authors: Amit Chakrabarti, Themistoklis Haris

Abstract: We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a $k$-uniform hypergraph $H$ with $n$ vertices and $m$ hyperedges. A $k$-simplex in $H$ is a subhypergraph on $k+1$ vertices $X$ such that all… ▽ More We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a $k$-uniform hypergraph $H$ with $n$ vertices and $m$ hyperedges. A $k$-simplex in $H$ is a subhypergraph on $k+1$ vertices $X$ such that all $k+1$ possible hyperedges among $X$ exist in $H$. The goal is to process a stream of hyperedges of $H$ and compute a good estimate of $T_k(H)$, the number of $k$-simplices in $H$. We design a suite of algorithms for this problem. Under a promise that $T_k(H) \ge T$, our algorithms use at most four passes and together imply a space bound of $O( ε^{-2} \logδ^{-1} \text{polylog} n \cdot \min\{ m^{1+1/k}/T, m/T^{2/(k+1)} \} )$ for each fixed $k \ge 3$, in order to guarantee an estimate within $(1\pmε)T_k(H)$ with probability at least $1-δ$. We also give a simpler $1$-pass algorithm that achieves $O(ε^{-2} \logδ^{-1} \log n\cdot (m/T) ( Δ_E + Δ_V^{1-1/k} ))$ space, where $Δ_E$ (respectively, $Δ_V$) denotes the maximum number of $k$-simplices that share a hyperedge (respectively, a vertex). We complement these algorithmic results with space lower bounds of the form $Ω(ε^{-2})$, $Ω(m^{1+1/k}/T)$, $Ω(m/T^{1-1/k})$ and $Ω(mΔ_V^{1/k}/T)$ for multi-pass algorithms and $Ω(mΔ_E/T)$ for $1$-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs. △ Less

Submitted 21 December, 2021; originally announced December 2021.

PROVES: Establishing Image Provenance using Semantic Signatures

Authors: Mingyang Xie, Manav Kulshrestha, Shaojie Wang, Jinghan Yang, Ayan Chakrabarti, Ning Zhang, Yevgeniy Vorobeychik

Abstract: Modern AI tools, such as generative adversarial networks, have transformed our ability to create and modify visual data with photorealistic results. However, one of the deleterious side-effects of these advances is the emergence of nefarious uses in manipulating information in visual data, such as through the use of deep fakes. We propose a novel architecture for preserving the provenance of seman… ▽ More Modern AI tools, such as generative adversarial networks, have transformed our ability to create and modify visual data with photorealistic results. However, one of the deleterious side-effects of these advances is the emergence of nefarious uses in manipulating information in visual data, such as through the use of deep fakes. We propose a novel architecture for preserving the provenance of semantic information in images to make them less susceptible to deep fake attacks. Our architecture includes semantic signing and verification steps. We apply this architecture to verifying two types of semantic information: individual identities (faces) and whether the photo was taken indoors or outdoors. Verification accounts for a collection of common image transformation, such as translation, scaling, cropping, and small rotations, and rejects adversarial transformations, such as adversarially perturbed or, in the case of face verification, swapped faces. Experiments demonstrate that in the case of provenance of faces in an image, our approach is robust to black-box adversarial transformations (which are rejected) as well as benign transformations (which are accepted), with few false negatives and false positives. Background verification, on the other hand, is susceptible to black-box adversarial examples, but becomes significantly more robust after adversarial training. △ Less

Submitted 21 October, 2021; originally announced October 2021.

Leveraging redundancy in attention with Reuse Transformers

Authors: Srinadh Bhojanapalli, Ayan Chakrabarti, Andreas Veit, Michal Lukasik, Himanshu Jain, Frederick Liu, Yin-Wen Chang, Sanjiv Kumar

Abstract: Pairwise dot product-based attention allows Transformers to exchange information between tokens in an input-dependent way, and is key to their success across diverse applications in language and vision. However, a typical Transformer model computes such pairwise attention scores repeatedly for the same sequence, in multiple heads in multiple layers. We systematically analyze the empirical similari… ▽ More Pairwise dot product-based attention allows Transformers to exchange information between tokens in an input-dependent way, and is key to their success across diverse applications in language and vision. However, a typical Transformer model computes such pairwise attention scores repeatedly for the same sequence, in multiple heads in multiple layers. We systematically analyze the empirical similarity of these scores across heads and layers and find them to be considerably redundant, especially adjacent layers showing high similarity. Motivated by these findings, we propose a novel architecture that reuses attention scores computed in one layer in multiple subsequent layers. Experiments on a number of standard benchmarks show that reusing attention delivers performance equivalent to or better than standard transformers, while reducing both compute and memory usage. △ Less

Submitted 13 October, 2021; originally announced October 2021.

Quantum solutions to possible challenges of Blockchain technology

Authors: Nivedita Dey, Mrityunjay Ghosh, Amlan Chakrabarti

Abstract: Technological advancements of Blockchain and other Distributed Ledger Techniques (DLTs) promise to provide significant advantages to applications seeking transparency, redundancy, and accountability. Actual adoption of these emerging technologies requires incorporating cost-effective, fast, QoS-enabled, secure, and scalable design. With the recent advent of quantum computing, the security of curre… ▽ More Technological advancements of Blockchain and other Distributed Ledger Techniques (DLTs) promise to provide significant advantages to applications seeking transparency, redundancy, and accountability. Actual adoption of these emerging technologies requires incorporating cost-effective, fast, QoS-enabled, secure, and scalable design. With the recent advent of quantum computing, the security of current blockchain cryptosystems can be compromised to a greater extent. Quantum algorithms like Shor's large integer factorization algorithm and Grover's unstructured database search algorithm can provide exponential and quadratic speedup, respectively, in contrast to their classical counterpart. This can put threats on both public-key cryptosystems and hash functions, which necessarily demands to migrate from classical cryptography to quantum-secure cryptography. Moreover, the computational latency of blockchain platforms causes slow transaction speed, so quantum computing principles might provide significant speedup and scalability in transaction processing and accelerating the mining process. For such purpose, this article first studies current and future classical state-of-the-art blockchain scalability and security primitives. The relevant quantum-safe blockchain cryptosystem initiatives which have been taken by Bitcoin, Ethereum, Corda, etc. are stated and compared with respect to key sizes, hash length, execution time, computational overhead, and energy efficiency. Post Quantum Cryptographic algorithms like Code-based, Lattice-based, Multivariate-based, and other schemes are not well suited for classical blockchain technology due to several disadvantages in practical implementation. Decryption latency, massive consumption of computational resources, and increased key size are few challenges that can hinder blockchain performance. △ Less

Submitted 11 October, 2021; originally announced October 2021.

Adversarially Robust Coloring for Graph Streams

Authors: Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

Abstract: A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an… ▽ More A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an $n$-vertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most $Δ$ and aim for colorings using a small number $f(Δ)$ of colors. A recent breakthrough (Assadi, Chen, and Khanna; SODA~2019) shows that in the standard, non-robust, streaming setting, $(Δ+1)$-colorings can be obtained while using only $\widetilde{O}(n)$ space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost $Ω(Δ^2)$ colors and that robust $O(Δ)$-coloring requires a linear amount of space, namely $Ω(nΔ)$. We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexity-theoretic standpoint, these lower bounds provide (i)~the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams and (ii)~the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust. We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an $O(Δ^2)$-coloring using $\widetilde{O}(n \sqrtΔ)$ space and an $O(Δ^3)$-coloring using $\widetilde{O}(n)$ space. △ Less

Submitted 22 September, 2021; originally announced September 2021.

The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries

Authors: Amit Chakrabarti, Manuel Stoeckl

Abstract: Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to access a massive input. Typically, algorithms in the former paradigm are non-adaptive whereas those in the latter are highly adaptive. This work studies the fundamental search problem of \textsc{element-extraction} in a q… ▽ More Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to access a massive input. Typically, algorithms in the former paradigm are non-adaptive whereas those in the latter are highly adaptive. This work studies the fundamental search problem of \textsc{element-extraction} in a query model that combines both: linear measurements with bounded adaptivity. In the \textsc{element-extraction} problem, one is given a nonzero vector $\mathbf{z} = (z_1,\ldots,z_n) \in \{0,1\}^n$ and must report an index $i$ where $z_i = 1$. The input can be accessed using arbitrary linear functions of it with coefficients in some ring. This problem admits an efficient nonadaptive randomized solution (through the well known technique of $\ell_0$-sampling) and an efficient fully adaptive deterministic solution (through binary search). We prove that when confined to only $k$ rounds of adaptivity, a deterministic \textsc{element-extraction} algorithm must spend $Ω(k (n^{1/k} -1))$ queries, when working in the ring of integers modulo some fixed $q$. This matches the corresponding upper bound. For queries using integer arithmetic, we prove a $2$-round $\widetildeΩ(\sqrt{n})$ lower bound, also tight up to polylogarithmic factors. Our proofs reduce to classic problems in combinatorics, and take advantage of established results on the {\em zero-sum problem} as well as recent improvements to the {\em sunflower lemma}. △ Less

Submitted 12 July, 2021; originally announced July 2021.

Eigen Analysis of Self-Attention and its Reconstruction from Partial Computation

Authors: Srinadh Bhojanapalli, Ayan Chakrabarti, Himanshu Jain, Sanjiv Kumar, Michal Lukasik, Andreas Veit

Abstract: State-of-the-art transformer models use pairwise dot-product based self-attention, which comes at a computational cost quadratic in the input sequence length. In this paper, we investigate the global structure of attention scores computed using this dot product mechanism on a typical distribution of inputs, and study the principal components of their variation. Through eigen analysis of full atten… ▽ More State-of-the-art transformer models use pairwise dot-product based self-attention, which comes at a computational cost quadratic in the input sequence length. In this paper, we investigate the global structure of attention scores computed using this dot product mechanism on a typical distribution of inputs, and study the principal components of their variation. Through eigen analysis of full attention score matrices, as well as of their individual rows, we find that most of the variation among attention scores lie in a low-dimensional eigenspace. Moreover, we find significant overlap between these eigenspaces for different layers and even different transformer models. Based on this, we propose to compute scores only for a partial subset of token pairs, and use them to estimate scores for the remaining pairs. Beyond investigating the accuracy of reconstructing attention scores themselves, we investigate training transformer models that employ these approximations, and analyze the effect on overall accuracy. Our analysis and the proposed method provide insights into how to balance the benefits of exact pair-wise attention and its significant computational expense. △ Less

Submitted 16 June, 2021; originally announced June 2021.

Comments: 14 pages

Circuit Design for $k$-coloring Problem and Its Implementation in Any Dimensional Quantum System

Authors: Amit Saha, Debasri Saha, Amlan Chakrabarti

Abstract: With the evolution of quantum computing, researchers now-a-days tend to incline to find solutions to NP-complete problems by using quantum algorithms in order to gain asymptotic advantage. In this paper, we solve $k$-coloring problem (NP-complete problem) using Grover's algorithm in any dimensional quantum system or any $d$-ary quantum system for the first time to the best of our knowledge, where… ▽ More With the evolution of quantum computing, researchers now-a-days tend to incline to find solutions to NP-complete problems by using quantum algorithms in order to gain asymptotic advantage. In this paper, we solve $k$-coloring problem (NP-complete problem) using Grover's algorithm in any dimensional quantum system or any $d$-ary quantum system for the first time to the best of our knowledge, where $d \ge 2$. A newly proposed comparator-based approach helps to generalize the implementation of the $k$-coloring problem in any dimensional quantum system. Till date, $k$-coloring problem has been implemented only in binary and ternary quantum system, hence, we abide to $d=2$ or $d=3$, that is for binary and ternary quantum system for comparing our proposed work with the state-of-the-art techniques. This proposed approach makes the reduction of the qubit cost possible, compared to the state-of-the-art binary quantum systems. Further, with the help of newly proposed ternary comparator, a substantial reduction in quantum gate count for the ternary oracle circuit of the $k$-coloring problem than the previous approaches has been obtained. An end-to-end automated framework has been put forward for implementing the $k$-coloring problem for any undirected and unweighted graph on any available Near-term quantum devices or Noisy Intermediate-Scale Quantum (NISQ) devices or multi-valued quantum simulator, which helps in generalizing our approach. △ Less

Submitted 29 May, 2021; originally announced May 2021.

Comments: 24 pages, 18 figures. arXiv admin note: text overlap with arXiv:2009.06073

Journal ref: SN COMPUT. SCI. 2, 427 (2021)

Vertex Ordering Problems in Directed Graph Streams

Authors: Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova

Abstract: We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-order… ▽ More We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-ordered and randomly-ordered streams. For arbitrary input graphs with edges ordered adversarially, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some lower bounds also apply when the stream is randomly ordered: e.g., in our most technical result we show that testing acyclicity in the $p$-pass random-order model requires roughly $n^{1+1/p}$ space. For other problems, random ordering can make a dramatic difference: e.g., it is possible to find a sink in an acyclic tournament in the one-pass random-order model using polylog$(n)$ space whereas under adversarial ordering roughly $n^{1/p}$ space is necessary and sufficient given $Θ(p)$ passes. We also design sublinear algorithms for the feedback arc set problem in tournament graphs; for random graphs; and for randomly ordered streams. In some cases, we give lower bounds establishing that our algorithms are essentially space-optimal. Together, our results complement the much maturer body of work on algorithms for undirected graph streams. △ Less

Submitted 17 May, 2021; originally announced May 2021.

Comments: Appeared in SODA 2020

Distantly Supervised Transformers For E-Commerce Product QA

Authors: Happy Mittal, Aniket Chakrabarti, Belhassen Bayar, Animesh Anant Sharma, Nikhil Rasiwasia

Abstract: We propose a practical instant question answering (QA) system on product pages of ecommerce services, where for each user query, relevant community question answer (CQA) pairs are retrieved. User queries and CQA pairs differ significantly in language characteristics making relevance learning difficult. Our proposed transformer-based model learns a robust relevance function by jointly learning unif… ▽ More We propose a practical instant question answering (QA) system on product pages of ecommerce services, where for each user query, relevant community question answer (CQA) pairs are retrieved. User queries and CQA pairs differ significantly in language characteristics making relevance learning difficult. Our proposed transformer-based model learns a robust relevance function by jointly learning unified syntactic and semantic representations without the need for human labeled data. This is achieved by distantly supervising our model by distilling from predictions of a syntactic matching system on user queries and simultaneously training with CQA pairs. Training with CQA pairs helps our model learning semantic QA relevance and distant supervision enables learning of syntactic features as well as the nuances of user querying language. Additionally, our model encodes queries and candidate responses independently allowing offline candidate embedding generation thereby minimizing the need for real-time transformer model execution. Consequently, our framework is able to scale to large e-commerce QA traffic. Extensive evaluation on user queries shows that our framework significantly outperforms both syntactic and semantic baselines in offline as well as large scale online A/B setups of a popular e-commerce service. △ Less

Submitted 7 April, 2021; originally announced April 2021.

Comments: NAACL 2021 (10 pages)

Understanding Robustness of Transformers for Image Classification

Authors: Srinadh Bhojanapalli, Ayan Chakrabarti, Daniel Glasner, Daliang Li, Thomas Unterthiner, Andreas Veit

Abstract: Deep Convolutional Neural Networks (CNNs) have long been the architecture of choice for computer vision tasks. Recently, Transformer-based architectures like Vision Transformer (ViT) have matched or even surpassed ResNets for image classification. However, details of the Transformer architecture -- such as the use of non-overlapping patches -- lead one to wonder whether these networks are as robus… ▽ More Deep Convolutional Neural Networks (CNNs) have long been the architecture of choice for computer vision tasks. Recently, Transformer-based architectures like Vision Transformer (ViT) have matched or even surpassed ResNets for image classification. However, details of the Transformer architecture -- such as the use of non-overlapping patches -- lead one to wonder whether these networks are as robust. In this paper, we perform an extensive study of a variety of different measures of robustness of ViT models and compare the findings to ResNet baselines. We investigate robustness to input perturbations as well as robustness to model perturbations. We find that when pre-trained with a sufficient amount of data, ViT models are at least as robust as the ResNet counterparts on a broad range of perturbations. We also find that Transformers are robust to the removal of almost any single layer, and that while activations from later layers are highly correlated with each other, they nevertheless play an important role in classification. △ Less

Submitted 8 October, 2021; v1 submitted 26 March, 2021; originally announced March 2021.

Comments: Accepted for publication at ICCV 2021. Rewrote Section 5 and made other minor changes throughout

Towards Power Efficient DNN Accelerator Design on Reconfigurable Platform

Authors: Rourab Paul, Sreetama Sarkar, Suman Sau, Koushik Chakraborty, Sanghamitra Roy, Amlan Chakrabarti

Abstract: The exponential emergence of Field Programmable Gate Array (FPGA) has accelerated the research of hardware implementation of Deep Neural Network (DNN). Among all DNN processors, domain specific architectures, such as, Google's Tensor Processor Unit (TPU) have outperformed conventional GPUs. However, implementation of TPUs in reconfigurable hardware should emphasize energy savings to serve the gree… ▽ More The exponential emergence of Field Programmable Gate Array (FPGA) has accelerated the research of hardware implementation of Deep Neural Network (DNN). Among all DNN processors, domain specific architectures, such as, Google's Tensor Processor Unit (TPU) have outperformed conventional GPUs. However, implementation of TPUs in reconfigurable hardware should emphasize energy savings to serve the green computing requirement. Voltage scaling, a popular approach towards energy savings, can be a bit critical in FPGA as it may cause timing failure if not done in an appropriate way. In this work, we present an ultra low power FPGA implementation of a TPU for edge applications. We divide the systolic-array of a TPU into different FPGA partitions, where each partition uses different near threshold (NTC) biasing voltages to run its FPGA cores. The biasing voltage for each partition is roughly calculated by the proposed static schemes. However, further calibration of biasing voltage is done by the proposed runtime scheme. Four clustering algorithms based on the minimum slack value of different design paths of Multiply Accumulates (MACs) study the partitioning of FPGA. To overcome the timing failure caused by NTC, the MACs which have higher minimum slack are placed in lower voltage partitions and the MACs have lower minimum slack path are placed in higher voltage partitions. The proposed architecture is simulated in a commercial platform : Vivado with Xilinx Artix-7 FPGA and academic platform VTR with 22nm, 45nm, 130nm FPGAs. The simulation results substantiate the implementation of voltage scaled TPU in FPGAs and also justifies its power efficiency. △ Less

Submitted 14 February, 2022; v1 submitted 13 February, 2021; originally announced February 2021.

Comments: Manuscript

Sparsistent filtering of comovement networks from high-dimensional data

Authors: Arnab Chakrabarti, Anindya S. Chakrabarti

Abstract: Network filtering is an important form of dimension reduction to isolate the core constituents of large and interconnected complex systems. We introduce a new technique to filter large dimensional networks arising out of dynamical behavior of the constituent nodes, exploiting their spectral properties. As opposed to the well known network filters that rely on preserving key topological properties… ▽ More Network filtering is an important form of dimension reduction to isolate the core constituents of large and interconnected complex systems. We introduce a new technique to filter large dimensional networks arising out of dynamical behavior of the constituent nodes, exploiting their spectral properties. As opposed to the well known network filters that rely on preserving key topological properties of the realized network, our method treats the spectrum as the fundamental object and preserves spectral properties. Applying asymptotic theory for high dimensional data for the filter, we show that it can be tuned to interpolate between zero filtering to maximal filtering that induces sparsity and consistency while having the least spectral distance from a linear shrinkage estimator. We apply our proposed filter to covariance networks constructed from financial data, to extract the key subnetwork embedded in the full sample network. △ Less

Submitted 22 January, 2021; originally announced January 2021.

Comments: 31 pages, 6 figures

A 55-line code for large-scale parallel topology optimization in 2D and 3D

Authors: Abhinav Gupta, Rajib Chowdhury, Anupam Chakrabarti, Timon Rabczuk

Abstract: This paper presents a 55-line code written in python for 2D and 3D topology optimization (TO) based on the open-source finite element computing software (FEniCS), equipped with various finite element tools and solvers. PETSc is used as the linear algebra back-end, which results in significantly less computational time than standard python libraries. The code is designed based on the popular solid… ▽ More This paper presents a 55-line code written in python for 2D and 3D topology optimization (TO) based on the open-source finite element computing software (FEniCS), equipped with various finite element tools and solvers. PETSc is used as the linear algebra back-end, which results in significantly less computational time than standard python libraries. The code is designed based on the popular solid isotropic material with penalization (SIMP) methodology. Extensions to multiple load cases, different boundary conditions, and incorporation of passive elements are also presented. Thus, this implementation is the most compact implementation of SIMP based topology optimization for 3D as well as 2D problems. Utilizing the concept of Euclidean distance matrix to vectorize the computation of the weight matrix for the filter, we have achieved a substantial reduction in the computational time and have also made it possible for the code to work with complex ground structure configurations. We have also presented the code's extension to large-scale topology optimization problems with support for parallel computations on complex structural configuration, which could help students and researchers explore novel insights into the TO problem with dense meshes. Appendix-A contains the complete code, and the website: \url{https://github.com/iitrabhi/topo-fenics} also contains the complete code. △ Less

Submitted 15 December, 2020; originally announced December 2020.

Deep Denoising of Flash and No-Flash Pairs for Photography in Low-Light Environments

Authors: Zhihao Xia, Michaël Gharbi, Federico Perazzi, Kalyan Sunkavalli, Ayan Chakrabarti

Abstract: We introduce a neural network-based method to denoise pairs of images taken in quick succession, with and without a flash, in low-light environments. Our goal is to produce a high-quality rendering of the scene that preserves the color and mood from the ambient illumination of the noisy no-flash image, while recovering surface texture and detail revealed by the flash. Our network outputs a gain ma… ▽ More We introduce a neural network-based method to denoise pairs of images taken in quick succession, with and without a flash, in low-light environments. Our goal is to produce a high-quality rendering of the scene that preserves the color and mood from the ambient illumination of the noisy no-flash image, while recovering surface texture and detail revealed by the flash. Our network outputs a gain map and a field of kernels, the latter obtained by linearly mixing elements of a per-image low-rank kernel basis. We first apply the kernel field to the no-flash image, and then multiply the result with the gain map to create the final output. We show our network effectively learns to produce high-quality images by combining a smoothed out estimate of the scene's ambient appearance from the no-flash image, with high-frequency albedo details extracted from the flash input. Our experiments show significant improvements over alternative captures without a flash, and baseline denoisers that use flash no-flash pairs. In particular, our method produces images that are both noise-free and contain accurate ambient colors without the sharp shadows or strong specular highlights visible in the flash image. △ Less

Submitted 14 April, 2021; v1 submitted 9 December, 2020; originally announced December 2020.

Comments: CVPR 2021. Project page at https://www.cse.wustl.edu/~zhihao.xia/deepfnf/

Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate

Authors: Amit Saha, Ritajit Majumdar, Debasri Saha, Amlan Chakrabarti, Susmita Sur-Kolay

Abstract: The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides considerable speed-up over classical paradigm. Further, Grover's algorithm can be extended to a $d$-ary (qudit) quantum system for utilizing the advantage of larger state space, which helps to reduce the run-time of the algorithm as co… ▽ More The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides considerable speed-up over classical paradigm. Further, Grover's algorithm can be extended to a $d$-ary (qudit) quantum system for utilizing the advantage of larger state space, which helps to reduce the run-time of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an $n$-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized $n$-qudit Toffoli gate has been realized using higher dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any $d$-ary quantum system, where $d \ge 2$, with the proposed $n$-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an $n$-qudit Toffoli gate requires access to two immediately higher energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant as we have reduced both gate count and circuit depth as compared to that in state-of-the-art works. △ Less

Submitted 18 May, 2022; v1 submitted 8 December, 2020; originally announced December 2020.

Comments: 15 pages, 9 figures

Journal ref: Phys. Rev. A, volume: 105 (2022)

Real-Time Edge Classification: Optimal Offloading under Token Bucket Constraints

Authors: Ayan Chakrabarti, Roch Guérin, Chenyang Lu, Jiangnan Liu

Abstract: To deploy machine learning-based algorithms for real-time applications with strict latency constraints, we consider an edge-computing setting where a subset of inputs are offloaded to the edge for processing by an accurate but resource-intensive model, and the rest are processed only by a less-accurate model on the device itself. Both models have computational costs that match available compute re… ▽ More To deploy machine learning-based algorithms for real-time applications with strict latency constraints, we consider an edge-computing setting where a subset of inputs are offloaded to the edge for processing by an accurate but resource-intensive model, and the rest are processed only by a less-accurate model on the device itself. Both models have computational costs that match available compute resources, and process inputs with low-latency. But offloading incurs network delays, and to manage these delays to meet application deadlines, we use a token bucket to constrain the average rate and burst length of transmissions from the device. We introduce a Markov Decision Process-based framework to make offload decisions under these constraints, based on the local model's confidence and the token bucket state, with the goal of minimizing a specified error measure for the application. Beyond isolated decisions for individual devices, we also propose approaches to allow multiple devices connected to the same access switch to share their bursting allocation. We evaluate and analyze the policies derived using our framework on the standard ImageNet image classification benchmark. △ Less

Submitted 5 November, 2020; v1 submitted 26 October, 2020; originally announced October 2020.

Comments: Code available at https://github.com/ayanc/edgeml.mdp

Finding Physical Adversarial Examples for Autonomous Driving with Fast and Differentiable Image Compositing

Authors: Jinghan Yang, Adith Boloor, Ayan Chakrabarti, Xuan Zhang, Yevgeniy Vorobeychik

Abstract: There is considerable evidence that deep neural networks are vulnerable to adversarial perturbations applied directly to their digital inputs. However, it remains an open question whether this translates to vulnerabilities in real systems. For example, an attack on self-driving cars would in practice entail modifying the driving environment, which then impacts the video inputs to the car's control… ▽ More There is considerable evidence that deep neural networks are vulnerable to adversarial perturbations applied directly to their digital inputs. However, it remains an open question whether this translates to vulnerabilities in real systems. For example, an attack on self-driving cars would in practice entail modifying the driving environment, which then impacts the video inputs to the car's controller, thereby indirectly leading to incorrect driving decisions. Such attacks require accounting for system dynamics and tracking viewpoint changes. We propose a scalable approach for finding adversarial modifications of a simulated autonomous driving environment using a differentiable approximation for the mapping from environmental modifications (rectangles on the road) to the corresponding video inputs to the controller neural network. Given the parameters of the rectangles, our proposed differentiable mapping composites them onto pre-recorded video streams of the original environment, accounting for geometric and color variations. Moreover, we propose a multiple trajectory sampling approach that enables our attacks to be robust to a car's self-correcting behavior. When combined with a neural network-based controller, our approach allows the design of adversarial modifications through end-to-end gradient-based optimization. Using the Carla autonomous driving simulator, we show that our approach is significantly more scalable and far more effective at identifying autonomous vehicle vulnerabilities in simulation experiments than a state-of-the-art approach based on Bayesian Optimization. △ Less

Submitted 10 June, 2021; v1 submitted 17 October, 2020; originally announced October 2020.

QDLC -- The Quantum Development Life Cycle

Authors: Nivedita Dey, Mrityunjay Ghosh, Subhra Samir kundu, Amlan Chakrabarti

Abstract: The magnificence grandeur of quantum computing lies in the inherent nature of quantum particles to exhibit true parallelism, which can be realized by indubitably fascinating theories of quantum physics. The possibilities opened by quantum computation (QC) is no where analogous to any classical simulation as quantum computers can efficiently simulate the complex dynamics of strongly correlated inte… ▽ More The magnificence grandeur of quantum computing lies in the inherent nature of quantum particles to exhibit true parallelism, which can be realized by indubitably fascinating theories of quantum physics. The possibilities opened by quantum computation (QC) is no where analogous to any classical simulation as quantum computers can efficiently simulate the complex dynamics of strongly correlated inter-facial systems. But, unfolding mysteries and leading to revolutionary breakthroughs in quantum computing are often challenged by lack of research and development potential in developing qubits with longer coherence interval, scaling qubit count, incorporating quantum error correction to name a few. Putting the first footstep into explorative quantum research by researchers and developers is also inherently ambiguous - due to lack of definitive steps in building up a quantum enabled customized computing stack. Difference in behavioral pattern of underlying system, early-stage noisy device, implementation barriers and performance metric cause hindrance in full adoption of existing classical SDLC suites for quantum product development. This in turn, necessitates to devise systematic and cost-effective techniques to quantum software development through a Quantum Development Life Cycle (QDLC) model, specifying the distinguished features and functionalities of quantum feasibility study, quantum requirement specification, quantum system design, quantum software coding and implementation, quantum testing and quantum software quality management. △ Less

Submitted 15 October, 2020; originally announced October 2020.

Comments: 18 pages, 4 tables, 6 diagrams

A Novel Quantum Algorithm for Ant Colony Optimization

Authors: Mrityunjay Ghosh, Nivedita Dey, Debdeep Mitra, Amlan Chakrabarti

Abstract: Ant colony optimization (ACO) is a commonly used meta-heuristic to solve complex combinatorial optimization problems like traveling salesman problem (TSP), vehicle routing problem (VRP), etc. However, classical ACO algorithms provide better optimal solutions but do not reduce computation time overhead to a significant extent. Algorithmic speed-up can be achieved by using parallelism offered by qua… ▽ More Ant colony optimization (ACO) is a commonly used meta-heuristic to solve complex combinatorial optimization problems like traveling salesman problem (TSP), vehicle routing problem (VRP), etc. However, classical ACO algorithms provide better optimal solutions but do not reduce computation time overhead to a significant extent. Algorithmic speed-up can be achieved by using parallelism offered by quantum computing. Existing quantum algorithms to solve ACO are either quantum-inspired classical algorithms or hybrid quantum-classical algorithms. Since all these algorithms need the intervention of classical computing, leveraging the true potential of quantum computing on real quantum hardware remains a challenge. This paper's main contribution is to propose a fully quantum algorithm to solve ACO, enhancing the quantum information processing toolbox in the fault-tolerant quantum computing (FTQC) era. We have Solved the Single Source Single Destination (SSSD) shortest-path problem using our proposed adaptive quantum circuit for representing dynamic pheromone updating strategy in real IBMQ devices. Our quantum ACO technique can be further used as a quantum ORACLE to solve complex optimization problems in a fully quantum setup with significant speed up upon the availability of more qubits. △ Less

Submitted 4 September, 2021; v1 submitted 14 October, 2020; originally announced October 2020.

Comments: 13 pages, 13 figures

Journal ref: IET Quantum Communication 2021

Circuit Design for $k$-coloring Problem and Its Implementation on Near-term Quantum Devices

Authors: Amit Saha, Debasri Saha, Amlan Chakrabarti

Abstract: Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speed-up. As per the work on computational complexity by Karp \cite{karp}, if any of the NP-complete problem can be solved… ▽ More Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speed-up. As per the work on computational complexity by Karp \cite{karp}, if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, $k$-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement $k$-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the $k$-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach. △ Less

Submitted 9 July, 2021; v1 submitted 13 September, 2020; originally announced September 2020.

Comments: 6 pages, 15 figures

Journal ref: 2020 IEEE International Symposium on Smart Electronic Systems (iSES) (Formerly iNiS)

2D Qubit Placement of Quantum Circuits using LONGPATH

Authors: Mrityunjay Ghosh, Nivedita Dey, Debdeep Mitra, Amlan Chakrabarti

Abstract: In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of… ▽ More In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture. △ Less

Submitted 14 July, 2020; originally announced July 2020.

Comments: Advanced Computing and Systems for Security, SpringerLink, Volume 10

The Blockchain Based Auditor on Secret key Life Cycle in Reconfigurable Platform

Authors: Rourab Paul, Nimisha Ghosh, Amlan Chakrabarti, Prasant Mahapatra

Abstract: The growing sophistication of cyber attacks, vulnerabilities in high computing systems and increasing dependency on cryptography to protect our digital data make it more important to keep secret keys safe and secure. Few major issues on secret keys like incorrect use of keys, inappropriate storage of keys, inadequate protection of keys, insecure movement of keys, lack of audit logging, insider thr… ▽ More The growing sophistication of cyber attacks, vulnerabilities in high computing systems and increasing dependency on cryptography to protect our digital data make it more important to keep secret keys safe and secure. Few major issues on secret keys like incorrect use of keys, inappropriate storage of keys, inadequate protection of keys, insecure movement of keys, lack of audit logging, insider threats and non-destruction of keys can compromise the whole security system dangerously. In this article, we have proposed and implemented an isolated secret key memory which can log life cycle of secret keys cryptographically using blockchain (BC) technology. We have also implemented a special custom bus interconnect which receives custom crypto instruction from Processing Element (PE). During the execution of crypto instructions, the architecture assures that secret key will never come in the processor area and the movement of secret keys to various crypto core is recorded cryptographically after the proper authentication process controlled by proposed hardware based BC. To the best of our knowledge, this is the first work which uses blockchain based solution to address the issues of the life cycle of the secret keys in hardware platform. The additional cost of resource usage and timing complexity we spent to implement the proposed idea is very nominal. We have used Xilinx Vivado EDA tool and Artix 7 FPGA board. △ Less

Submitted 13 July, 2020; originally announced July 2020.

Comments: Manuscript

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

Authors: Amit Chakrabarti, Prantar Ghosh, Justin Thaler

Abstract: We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provide… ▽ More We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier. This work designs new schemes for a number of basic graph problems---including triangle counting, maximum matching, topological sorting, and single-source shortest paths---where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors. Specifically, for most graph problems that we study, it is known that the product of the verifier's space cost $v$ and the proof length $h$ must be at least $Ω(n^2)$ for $n$-vertex graphs. However, matching upper bounds are only known for a handful of settings of $h$ and $v$ on the curve $h \cdot v=\tildeΘ(n^2)$. For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for $(h=\tilde{O}(n^2), v=\tilde{O}(1))$, $(h=\tilde{O}(n), v=\tilde{O}(n))$, and the trivial $(h=\tilde{O}(1), v=\tilde{O}(n^2))$. A major message of this work is that by exploiting nonlinear sketches, a significant ``portion'' of costs on the tradeoff curve $h \cdot v = n^2$ can be achieved. △ Less

Submitted 6 July, 2020; originally announced July 2020.

Adversarial Robustness of Deep Sensor Fusion Models

Authors: Shaojie Wang, Tong Wu, Ayan Chakrabarti, Yevgeniy Vorobeychik

Abstract: We experimentally study the robustness of deep camera-LiDAR fusion architectures for 2D object detection in autonomous driving. First, we find that the fusion model is usually both more accurate, and more robust against single-source attacks than single-sensor deep neural networks. Furthermore, we show that without adversarial training, early fusion is more robust than late fusion, whereas the two… ▽ More We experimentally study the robustness of deep camera-LiDAR fusion architectures for 2D object detection in autonomous driving. First, we find that the fusion model is usually both more accurate, and more robust against single-source attacks than single-sensor deep neural networks. Furthermore, we show that without adversarial training, early fusion is more robust than late fusion, whereas the two perform similarly after adversarial training. However, we note that single-channel adversarial training of deep fusion is often detrimental even to robustness. Moreover, we observe cross-channel externalities, where single-channel adversarial training reduces robustness to attacks on the other channel. Additionally, we observe that the choice of adversarial model in adversarial training is critical: using attacks restricted to cars' bounding boxes is more effective in adversarial training and exhibits less significant cross-channel externalities. Finally, we find that joint-channel adversarial training helps mitigate many of the issues above, but does not significantly boost adversarial robustness. △ Less

Submitted 11 April, 2022; v1 submitted 23 June, 2020; originally announced June 2020.

Circuit Design for Clique Problem and Its Implementation on Quantum Computer

Authors: Arpita Sanyal, Amit Saha, Debasri Saha, Banani Saha, Amlan Chakrabarti

Abstract: Finding cliques in a graph has several applications for its pattern matching ability. $k$-clique problem, a special case of clique problem, determines whether an arbitrary graph contains a clique of size $k$, has already been addressed in quantum domain. A variant of $k$-clique problem that lists all cliques of size $k$, has also popular modern-day applications. Albeit, the implementation of such… ▽ More Finding cliques in a graph has several applications for its pattern matching ability. $k$-clique problem, a special case of clique problem, determines whether an arbitrary graph contains a clique of size $k$, has already been addressed in quantum domain. A variant of $k$-clique problem that lists all cliques of size $k$, has also popular modern-day applications. Albeit, the implementation of such variant of $k$-clique problem in quantum setting still remains untouched. In this paper, apart from theoretical solution of such $k$-clique problem, practical quantum gate-based implementation has been addressed using Grover's algorithm. This approach is further extended to design circuit for the maximum clique problem in classical-quantum hybrid architecture. The algorithm automatically generates the circuit for any given undirected and unweighted graph and any given $k$, which makes our approach generalized in nature. The proposed approach of solving $k$-clique problem has exhibited a reduction of qubit cost and circuit depth as compared to the state-of-the-art approach, for a small $k$ with respect to a large graph. A framework that can map the automated generated circuit for clique problem to quantum devices is also proposed. An analysis of the experimental results is demonstrated using IBM's Qiskit. △ Less

Submitted 7 July, 2021; v1 submitted 10 March, 2020; originally announced April 2020.

Comments: 25 pages, 18 figures. arXiv admin note: text overlap with arXiv:1805.10224 by other authors

Journal ref: IET Quantum Communication, 2021

Towards a MEMS-based Adaptive LIDAR

Authors: Francesco Pittaluga, Zaid Tasneem, Justin Folden, Brevin Tilmon, Ayan Chakrabarti, Sanjeev J. Koppal

Abstract: We present a proof-of-concept LIDAR design that allows adaptive real-time measurements according to dynamically specified measurement patterns. We describe our optical setup and calibration, which enables fast sparse depth measurements using a scanning MEMS (micro-electro-mechanical) mirror. We validate the efficacy of our prototype LIDAR design by testing on over 75 static and dynamic scenes span… ▽ More We present a proof-of-concept LIDAR design that allows adaptive real-time measurements according to dynamically specified measurement patterns. We describe our optical setup and calibration, which enables fast sparse depth measurements using a scanning MEMS (micro-electro-mechanical) mirror. We validate the efficacy of our prototype LIDAR design by testing on over 75 static and dynamic scenes spanning a range of environments. We show CNN-based depth-map completion experiments which demonstrate that our sensor can realize adaptive depth sensing for dynamic scenes. △ Less

Submitted 16 October, 2020; v1 submitted 20 March, 2020; originally announced March 2020.

Comments: 14 pages, 5 figures, project site: https://www.fpittaluga.com/adaptivelidar, to be published in International Conference on 3D Vision 2020

Basis Prediction Networks for Effective Burst Denoising with Large Kernels

Authors: Zhihao Xia, Federico Perazzi, Michaël Gharbi, Kalyan Sunkavalli, Ayan Chakrabarti

Abstract: Bursts of images exhibit significant self-similarity across both time and space. This motivates a representation of the kernels as linear combinations of a small set of basis elements. To this end, we introduce a novel basis prediction network that, given an input burst, predicts a set of global basis kernels -- shared within the image -- and the corresponding mixing coefficients -- which are spec… ▽ More Bursts of images exhibit significant self-similarity across both time and space. This motivates a representation of the kernels as linear combinations of a small set of basis elements. To this end, we introduce a novel basis prediction network that, given an input burst, predicts a set of global basis kernels -- shared within the image -- and the corresponding mixing coefficients -- which are specific to individual pixels. Compared to state-of-the-art techniques that output a large tensor of per-pixel spatiotemporal kernels, our formulation substantially reduces the dimensionality of the network output. This allows us to effectively exploit comparatively larger denoising kernels, achieving both significant quality improvements (over 1dB PSNR) and faster run-times over state-of-the-art methods. △ Less

Submitted 2 December, 2020; v1 submitted 9 December, 2019; originally announced December 2019.

Comments: CVPR 2020. Project website at https://www.cse.wustl.edu/~zhihao.xia/bpn/