Showing 1–31 of 31 results for author: Choudhary, K

Judging the Judges: Evaluating Alignment and Vulnerabilities in LLMs-as-Judges

Authors: Aman Singh Thakur, Kartik Choudhary, Venkat Srinik Ramayapally, Sankaran Vaidyanathan, Dieuwke Hupkes

Abstract: Offering a promising solution to the scalability challenges associated with human evaluation, the LLM-as-a-judge paradigm is rapidly gaining traction as an approach to evaluating large language models (LLMs). However, there are still many open questions about the strengths and weaknesses of this paradigm, and what potential biases it may hold. In this paper, we present a comprehensive study of the… ▽ More Offering a promising solution to the scalability challenges associated with human evaluation, the LLM-as-a-judge paradigm is rapidly gaining traction as an approach to evaluating large language models (LLMs). However, there are still many open questions about the strengths and weaknesses of this paradigm, and what potential biases it may hold. In this paper, we present a comprehensive study of the performance of various LLMs acting as judges. We leverage TriviaQA as a benchmark for assessing objective knowledge reasoning of LLMs and evaluate them alongside human annotations which we found to have a high inter-annotator agreement. Our study includes 9 judge models and 9 exam taker models -- both base and instruction-tuned. We assess the judge model's alignment across different model sizes, families, and judge prompts. Among other results, our research rediscovers the importance of using Cohen's kappa as a metric of alignment as opposed to simple percent agreement, showing that judges with high percent agreement can still assign vastly different scores. We find that both Llama-3 70B and GPT-4 Turbo have an excellent alignment with humans, but in terms of ranking exam taker models, they are outperformed by both JudgeLM-7B and the lexical judge Contains, which have up to 34 points lower human alignment. Through error analysis and various other studies, including the effects of instruction length and leniency bias, we hope to provide valuable lessons for using LLMs as judges in the future. △ Less

Submitted 1 July, 2024; v1 submitted 18 June, 2024; originally announced June 2024.

ICU-Sepsis: A Benchmark MDP Built from Real Medical Data

Authors: Kartik Choudhary, Dhawal Gupta, Philip S. Thomas

Abstract: We present ICU-Sepsis, an environment that can be used in benchmarks for evaluating reinforcement learning (RL) algorithms. Sepsis management is a complex task that has been an important topic in applied RL research in recent years. Therefore, MDPs that model sepsis management can serve as part of a benchmark to evaluate RL algorithms on a challenging real-world problem. However, creating usable M… ▽ More We present ICU-Sepsis, an environment that can be used in benchmarks for evaluating reinforcement learning (RL) algorithms. Sepsis management is a complex task that has been an important topic in applied RL research in recent years. Therefore, MDPs that model sepsis management can serve as part of a benchmark to evaluate RL algorithms on a challenging real-world problem. However, creating usable MDPs that simulate sepsis care in the ICU remains a challenge due to the complexities involved in acquiring and processing patient data. ICU-Sepsis is a lightweight environment that models personalized care of sepsis patients in the ICU. The environment is a tabular MDP that is widely compatible and is challenging even for state-of-the-art RL algorithms, making it a valuable tool for benchmarking their performance. However, we emphasize that while ICU-Sepsis provides a standardized environment for evaluating RL algorithms, it should not be used to draw conclusions that guide medical practice. △ Less

Submitted 9 June, 2024; originally announced June 2024.

Comments: Reinforcement Learning Conference 2024

Fault-Tolerant Bounded Flow Preservers

Authors: Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, Harsh Wardhan

Abstract: Given a directed graph $G = (V, E)$ with $n$ vertices, $m$ edges and a designated source vertex $s\in V$, we consider the question of finding a sparse subgraph $H$ of $G$ that preserves the flow from $s$ up to a given threshold $λ$ even after failure of $k$ edges. We refer to such subgraphs as $(λ,k)$-fault-tolerant bounded-flow-preserver ($(λ,k)$-FT-BFP). Formally, for any $F \subseteq E$ of at m… ▽ More Given a directed graph $G = (V, E)$ with $n$ vertices, $m$ edges and a designated source vertex $s\in V$, we consider the question of finding a sparse subgraph $H$ of $G$ that preserves the flow from $s$ up to a given threshold $λ$ even after failure of $k$ edges. We refer to such subgraphs as $(λ,k)$-fault-tolerant bounded-flow-preserver ($(λ,k)$-FT-BFP). Formally, for any $F \subseteq E$ of at most $k$ edges and any $v\in V$, the $(s, v)$-max-flow in $H \setminus F$ is equal to $(s, v)$-max-flow in $G \setminus F$, if the latter is bounded by $λ$, and at least $λ$ otherwise. Our contributions are summarized as follows: 1. We provide a polynomial time algorithm that given any graph $G$ constructs a $(λ,k)$-FT-BFP of $G$ with at most $λ2^kn$ edges. 2. We also prove a matching lower bound of $Ω(λ2^kn)$ on the size of $(λ,k)$-FT-BFP. In particular, we show that for every $λ,k,n\geq 1$, there exists an $n$-vertex directed graph whose optimal $(λ,k)$-FT-BFP contains $Ω(\min\{2^kλn,n^2\})$ edges. 3. Furthermore, we show that the problem of computing approximate $(λ,k)$-FT-BFP is NP-hard for any approximation ratio that is better than $O(\log(λ^{-1} n))$. △ Less

Submitted 24 April, 2024; originally announced April 2024.

Comments: 12 pages, 2 figures

Factorized Motion Fields for Fast Sparse Input Dynamic View Synthesis

Authors: Nagabhushan Somraj, Kapil Choudhary, Sai Harsha Mupparaju, Rajiv Soundararajan

Abstract: Designing a 3D representation of a dynamic scene for fast optimization and rendering is a challenging task. While recent explicit representations enable fast learning and rendering of dynamic radiance fields, they require a dense set of input viewpoints. In this work, we focus on learning a fast representation for dynamic radiance fields with sparse input viewpoints. However, the optimization with… ▽ More Designing a 3D representation of a dynamic scene for fast optimization and rendering is a challenging task. While recent explicit representations enable fast learning and rendering of dynamic radiance fields, they require a dense set of input viewpoints. In this work, we focus on learning a fast representation for dynamic radiance fields with sparse input viewpoints. However, the optimization with sparse input is under-constrained and necessitates the use of motion priors to constrain the learning. Existing fast dynamic scene models do not explicitly model the motion, making them difficult to be constrained with motion priors. We design an explicit motion model as a factorized 4D representation that is fast and can exploit the spatio-temporal correlation of the motion field. We then introduce reliable flow priors including a combination of sparse flow priors across cameras and dense flow priors within cameras to regularize our motion model. Our model is fast, compact and achieves very good performance on popular multi-view dynamic scene datasets with sparse input viewpoints. The source code for our model can be found on our project page: https://nagabhushansn95.github.io/publications/2024/RF-DeRF.html. △ Less

Submitted 24 April, 2024; v1 submitted 17 April, 2024; originally announced April 2024.

Comments: Accepted at SIGGRAPH 2024

Approaches for Uncertainty Quantification of AI-predicted Material Properties: A Comparison

Authors: Francesca Tavazza, Kamal Choudhary, Brian DeCost

Abstract: The development of large databases of material properties, together with the availability of powerful computers, has allowed machine learning (ML) modeling to become a widely used tool for predicting material performances. While confidence intervals are commonly reported for such ML models, prediction intervals, i.e., the uncertainty on each prediction, are not as frequently available. Here, we in… ▽ More The development of large databases of material properties, together with the availability of powerful computers, has allowed machine learning (ML) modeling to become a widely used tool for predicting material performances. While confidence intervals are commonly reported for such ML models, prediction intervals, i.e., the uncertainty on each prediction, are not as frequently available. Here, we investigate three easy-to-implement approaches to determine such individual uncertainty, comparing them across ten ML quantities spanning energetics, mechanical, electronic, optical, and spectral properties. Specifically, we focused on the Quantile approach, the direct machine learning of the prediction intervals and Ensemble methods. △ Less

Submitted 19 October, 2023; originally announced October 2023.

Comments: arXiv admin note: substantial text overlap with arXiv:2107.07997

Interpretable Ensemble Learning for Materials Property Prediction with Classical Interatomic Potentials: Carbon as an Example

Authors: Xinyu Jiang, Haofan Sun, Kamal Choudhary, Houlong Zhuang, Qiong Nian

Abstract: Machine learning (ML) is widely used to explore crystal materials and predict their properties. However, the training is time-consuming for deep-learning models, and the regression process is a black box that is hard to interpret. Also, the preprocess to transfer a crystal structure into the input of ML, called descriptor, needs to be designed carefully. To efficiently predict important properties… ▽ More Machine learning (ML) is widely used to explore crystal materials and predict their properties. However, the training is time-consuming for deep-learning models, and the regression process is a black box that is hard to interpret. Also, the preprocess to transfer a crystal structure into the input of ML, called descriptor, needs to be designed carefully. To efficiently predict important properties of materials, we propose an approach based on ensemble learning consisting of regression trees to predict formation energy and elastic constants based on small-size datasets of carbon allotropes as an example. Without using any descriptor, the inputs are the properties calculated by molecular dynamics with 9 different classical interatomic potentials. Overall, the results from ensemble learning are more accurate than those from classical interatomic potentials, and ensemble learning can capture the relatively accurate properties from the 9 classical potentials as criteria for predicting the final properties. △ Less

Submitted 24 July, 2023; originally announced August 2023.

Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs

Authors: Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck

Abstract: Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stretch. A fundamental open problem is whether such a bound is achievable for distance oracles as well. Specifically, can we construct a distance oracle w… ▽ More Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stretch. A fundamental open problem is whether such a bound is achievable for distance oracles as well. Specifically, can we construct a distance oracle with multiplicative stretch better than 2, along with some additive stretch, while maintaining subquadratic space complexity? This question remains a crucial area of investigation, and finding a positive answer would be a significant step forward for distance oracles. Indeed, such oracles have been constructed for sparse graphs. However, in the more general case of dense graphs, it is currently unknown whether such oracles exist. In this paper, we contribute to the field by presenting the first distance oracles that achieve a multiplicative stretch of $1+\varepsilon$ along with a small additive stretch while maintaining subquadratic space complexity. Our results represent an advancement particularly for constructing efficient distance oracles for dense graphs. In addition, we present a whole family of oracles that, for any positive integer $k$, achieve a multiplicative stretch of $2k-1+\varepsilon$ using $o(n^{1+1/k})$ space. △ Less

Submitted 21 July, 2023; originally announced July 2023.

14 Examples of How LLMs Can Transform Materials Science and Chemistry: A Reflection on a Large Language Model Hackathon

Authors: Kevin Maik Jablonka, Qianxiang Ai, Alexander Al-Feghali, Shruti Badhwar, Joshua D. Bocarsly, Andres M Bran, Stefan Bringuier, L. Catherine Brinson, Kamal Choudhary, Defne Circi, Sam Cox, Wibe A. de Jong, Matthew L. Evans, Nicolas Gastellu, Jerome Genzling, María Victoria Gil, Ankur K. Gupta, Zhi Hong, Alishba Imran, Sabine Kruschwitz, Anne Labarre, Jakub Lála, Tao Liu, Steven Ma, Sauradeep Majumdar , et al. (28 additional authors not shown)

Abstract: Large-language models (LLMs) such as GPT-4 caught the interest of many scientists. Recent studies suggested that these models could be useful in chemistry and materials science. To explore these possibilities, we organized a hackathon. This article chronicles the projects built as part of this hackathon. Participants employed LLMs for various applications, including predicting properties of mole… ▽ More Large-language models (LLMs) such as GPT-4 caught the interest of many scientists. Recent studies suggested that these models could be useful in chemistry and materials science. To explore these possibilities, we organized a hackathon. This article chronicles the projects built as part of this hackathon. Participants employed LLMs for various applications, including predicting properties of molecules and materials, designing novel interfaces for tools, extracting knowledge from unstructured data, and developing new educational applications. The diverse topics and the fact that working prototypes could be generated in less than two days highlight that LLMs will profoundly impact the future of our fields. The rich collection of ideas and projects also indicates that the applications of LLMs are not limited to materials science and chemistry but offer potential benefits to a wide range of scientific disciplines. △ Less

Submitted 14 July, 2023; v1 submitted 9 June, 2023; originally announced June 2023.

On Color Critical Graphs of Star Coloring

Authors: Harshit Kumar Choudhary, I. Vinod Reddy

Abstract: A \emph{star coloring} of a graph $G$ is a proper vertex-coloring such that no path on four vertices is $2$-colored. The minimum number of colors required to obtain a star coloring of a graph $G$ is called star chromatic number and it is denoted by $χ_s(G)$. A graph $G$ is called $k$-critical if $χ_s(G)=k$ and $χ_s(G -e) < χ_s(G)$ for every edge $e \in E(G)$. In this paper, we give a characterizat… ▽ More A \emph{star coloring} of a graph $G$ is a proper vertex-coloring such that no path on four vertices is $2$-colored. The minimum number of colors required to obtain a star coloring of a graph $G$ is called star chromatic number and it is denoted by $χ_s(G)$. A graph $G$ is called $k$-critical if $χ_s(G)=k$ and $χ_s(G -e) < χ_s(G)$ for every edge $e \in E(G)$. In this paper, we give a characterization of 3-critical, $(n-1)$-critical and $(n-2)$-critical graphs with respect to star coloring, where $n$ denotes the number of vertices of $G$. We also give upper and lower bounds on the minimum number of edges in $(n-1)$-critical and $(n-2)$-critical graphs. △ Less

Submitted 29 May, 2023; originally announced May 2023.

Approximate Distance Sensitivity Oracles in Subquadratic Space

Authors: Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck

Abstract: An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $σ\ge 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a pair of vertices $s, t$ and a set $F$ of at most $f$ edges, it returns a $σ$-approximation of the $s$-$t$-distance in $G-F$. We study $f$-DSOs that take… ▽ More An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $σ\ge 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a pair of vertices $s, t$ and a set $F$ of at most $f$ edges, it returns a $σ$-approximation of the $s$-$t$-distance in $G-F$. We study $f$-DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for $σ\ge 3$. We present, for any constant $f \ge 1$ and $α\in (0, \frac{1}{2})$, and any $\varepsilon > 0$, a randomized $f$-DSO with stretch $ 3 + \varepsilon$ that w.h.p. takes $\widetilde{O}(n^{2-\fracα{f+1}}) \cdot O(\log n/\varepsilon)^{f+2}$ space and has an $O(n^α/\varepsilon^2)$ query time. The time to build the oracle is $\widetilde{O}(mn^{2-\fracα{f+1}}) \cdot O(\log n/\varepsilon)^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k-1$ that w.h.p. takes $O(D^{f+o(1)} n^{1+1/k})$ space and has $\widetilde{O}(D^{o(1)})$ query time, with a preprocessing time of $O(D^{f+o(1)} mn^{1/k})$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1{+}\varepsilon$ and preprocessing time $O(n^{5+o(1)}/\varepsilon^f)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O(mn^{2+o(1)}/\varepsilon^f)$. △ Less

Submitted 4 June, 2024; v1 submitted 19 May, 2023; originally announced May 2023.

Comments: The is the arXiv version of the eponymous paper that appeared first at STOC 2023 and then was extended to a journal version, published in TheoretiCS

Journal ref: TheoretiCS, Volume 3 (2024), Article 15, 1-47

Fault-Tolerant ST-Diameter Oracles

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck

Abstract: We study the problem of estimating the $ST$-diameter of a graph that is subject to a bounded number of edge failures. An $f$-edge fault-tolerant $ST$-diameter oracle ($f$-FDO-$ST$) is a data structure that preprocesses a given graph $G$, two sets of vertices $S,T$, and positive integer $f$. When queried with a set $F$ of at most $f$ edges, the oracle returns an estimate $\widehat{D}$ of the $ST$-d… ▽ More We study the problem of estimating the $ST$-diameter of a graph that is subject to a bounded number of edge failures. An $f$-edge fault-tolerant $ST$-diameter oracle ($f$-FDO-$ST$) is a data structure that preprocesses a given graph $G$, two sets of vertices $S,T$, and positive integer $f$. When queried with a set $F$ of at most $f$ edges, the oracle returns an estimate $\widehat{D}$ of the $ST$-diameter $\operatorname{diam}(G-F,S,T)$, the maximum distance between vertices in $S$ and $T$ in $G-F$. The oracle has stretch $σ\geq 1$ if $\operatorname{diam}(G-F,S,T) \leq \widehat{D} \leq σ\operatorname{diam}(G-F,S,T)$. If $S$ and $T$ both contain all vertices, the data structure is called an $f$-edge fault-tolerant diameter oracle ($f$-FDO). An $f$-edge fault-tolerant distance sensitivity oracles ($f$-DSO) estimates the pairwise graph distances under up to $f$ failures. We design new $f$-FDOs and $f$-FDO-$ST$s by reducing their construction to that of all-pairs and single-source $f$-DSOs. We obtain several new tradeoffs between the size of the data structure, stretch guarantee, query and preprocessing times for diameter oracles by combining our black-box reductions with known results from the literature. We also provide an information-theoretic lower bound on the space requirement of approximate $f$-FDOs. We show that there exists a family of graphs for which any $f$-FDO with sensitivity $f \ge 2$ and stretch less than $5/3$ requires $Ω(n^{3/2})$ bits of space, regardless of the query time. △ Less

Submitted 5 May, 2023; originally announced May 2023.

Comments: accepted at ICALP 2023

Compact Distance Oracles with Large Sensitivity and Low Stretch

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck

Abstract: An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $σ\geq 1$ is a data structure that preprocesses an input graph $G$. When queried with the triple $(s,t,F)$, where $s, t \in V$ and $F \subseteq E$ contains at most $f$ edges of $G$, the oracle returns an estimate $\widehat{d}_{G-F}(s,t)$ of the distance $d_{G-F}(s,t)$ between $s$ and $t$ in the graph $G-F$ such that… ▽ More An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $σ\geq 1$ is a data structure that preprocesses an input graph $G$. When queried with the triple $(s,t,F)$, where $s, t \in V$ and $F \subseteq E$ contains at most $f$ edges of $G$, the oracle returns an estimate $\widehat{d}_{G-F}(s,t)$ of the distance $d_{G-F}(s,t)$ between $s$ and $t$ in the graph $G-F$ such that $d_{G-F}(s,t) \leq \widehat{d}_{G-F}(s,t) \leq σd_{G-F}(s,t)$. For any positive integer $k \ge 2$ and any $0 < α< 1$, we present an $f$-DSO with sensitivity $f = o(\log n/\log\log n)$, stretch $2k-1$, space $O(n^{1+\frac{1}{k}+α+o(1)})$, and an $\widetilde{O}(n^{1+\frac{1}{k} - \fracα{k(f+1)}})$ query time. Prior to our work, there were only three known $f$-DSOs with subquadratic space. The first one by Chechik et al. [Algorithmica 2012] has a stretch of $(8k-2)(f+1)$, depending on $f$. Another approach is storing an $f$-edge fault-tolerant $(2k-1)$-spanner of $G$. The bottleneck is the large query time due to the size of any such spanner, which is $Ω(n^{1+1/k})$ under the Erdős girth conjecture. Bilò et al. [STOC 2023] gave a solution with stretch $3+\varepsilon$, query time $O(n^α)$ but space $O(n^{2-\fracα{f+1}})$, approaching the quadratic barrier for large sensitivity. In the realm of subquadratic space, our $f$-DSOs are the first ones that guarantee, at the same time, large sensitivity, low stretch, and non-trivial query time. To obtain our results, we use the approximate distance oracles of Thorup and Zwick [JACM 2005], and the derandomization of the $f$-DSO of Weimann and Yuster [TALG 2013], that was recently given by Karthik and Parter [SODA 2021]. △ Less

Submitted 27 April, 2023; originally announced April 2023.

Comments: accepted at WADS 2023

Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck

Abstract: We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccent… ▽ More We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time. △ Less

Submitted 22 April, 2022; originally announced April 2022.

Comments: Full version of an ICALP 2022 paper

Prediction of the electron density of states for crystalline compounds with Atomistic Line Graph Neural Networks (ALIGNN)

Authors: Prathik R Kaundinya, Kamal Choudhary, Surya R. Kalidindi

Abstract: Machine learning (ML) based models have greatly enhanced the traditional materials discovery and design pipeline. Specifically, in recent years, surrogate ML models for material property prediction have demonstrated success in predicting discrete scalar-valued target properties to within reasonable accuracy of their DFT-computed values. However, accurate prediction of spectral targets such as the… ▽ More Machine learning (ML) based models have greatly enhanced the traditional materials discovery and design pipeline. Specifically, in recent years, surrogate ML models for material property prediction have demonstrated success in predicting discrete scalar-valued target properties to within reasonable accuracy of their DFT-computed values. However, accurate prediction of spectral targets such as the electron Density of States (DOS) poses a much more challenging problem due to the complexity of the target, and the limited amount of available training data. In this study, we present an extension of the recently developed Atomistic Line Graph Neural Network (ALIGNN) to accurately predict DOS of a large set of material unit cell structures, trained to the publicly available JARVIS-DFT dataset. Furthermore, we evaluate two methods of representation of the target quantity - a direct discretized spectrum, and a compressed low-dimensional representation obtained using an autoencoder. Through this work, we demonstrate the utility of graph-based featurization and modeling methods in the prediction of complex targets that depend on both chemistry and directional characteristics of material structures. △ Less

Submitted 20 January, 2022; originally announced January 2022.

Fixed-Parameter Sensitivity Oracles

Authors: Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J. A. Gregor Lagodzinski, Martin Schirneck, Simon Wietheger

Abstract: We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f$ for an FPT problem $Π$ on a graph $G$ with parameter $k$ preprocesses $G$ in time $O(g(f,k) \cdot \textsf{poly}(n))$. When queried with a set $F$ of at most $f$ edges of $G$, the oracle reports the answer to the $Π$-wi… ▽ More We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f$ for an FPT problem $Π$ on a graph $G$ with parameter $k$ preprocesses $G$ in time $O(g(f,k) \cdot \textsf{poly}(n))$. When queried with a set $F$ of at most $f$ edges of $G$, the oracle reports the answer to the $Π$-with the same parameter $k$-on the graph $G-F$, i.e., $G$ deprived of $F$. The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on $G-F$ from scratch. We mainly design sensitivity oracles for the $k$-Path and the $k$-Vertex Cover problem. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we also introduce parameterization to the computation of distance preservers. We study the problem, given a directed unweighted graph with a fixed source $s$ and parameters $f$ and $k$, to construct a polynomial-sized oracle that efficiently reports, for any target vertex $v$ and set $F$ of at most $f$ edges, whether the distance from $s$ to $v$ increases at most by an additive term of $k$ in $G-F$. △ Less

Submitted 6 December, 2021; originally announced December 2021.

Comments: 19 pages, 1 figure, abstract shortened to meet ArXiv requirements; accepted at ITCS'22

Predicting Lattice Phonon Vibrational Frequencies Using Deep Graph Neural Networks

Authors: Nghia Nguyen, Steph-Yves Louis, Lai Wei, Kamal Choudhary, Ming Hu, Jianjun Hu

Abstract: Lattice vibration frequencies are related to many important materials properties such as thermal and electrical conductivity as well as superconductivity. However, computational calculation of vibration frequencies using density functional theory (DFT) methods is too computationally demanding for a large number of samples in materials screening. Here we propose a deep graph neural network-based al… ▽ More Lattice vibration frequencies are related to many important materials properties such as thermal and electrical conductivity as well as superconductivity. However, computational calculation of vibration frequencies using density functional theory (DFT) methods is too computationally demanding for a large number of samples in materials screening. Here we propose a deep graph neural network-based algorithm for predicting crystal vibration frequencies from crystal structures with high accuracy. Our algorithm addresses the variable dimension of vibration frequency spectrum using the zero padding scheme. Benchmark studies on two data sets with 15,000 and 35,552 samples show that the aggregated $R^2$ scores of the prediction reaches 0.554 and 0.724 respectively. Our work demonstrates the capability of deep graph neural networks to learn to predict phonon spectrum properties of crystal structures in addition to phonon density of states (DOS) and electronic DOS in which the output dimension is constant. △ Less

Submitted 10 November, 2021; originally announced November 2021.

Comments: 9 pages

Pairwise Reachability Oracles and Preservers under Failures

Authors: Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary

Abstract: In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let $G = (V, E)$ be a directed graph on $n$-nodes, and $P\subseteq V\times V$ be a set of vertex pairs in $G$. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we pro… ▽ More In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let $G = (V, E)$ be a directed graph on $n$-nodes, and $P\subseteq V\times V$ be a set of vertex pairs in $G$. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we provide extremal bounds for sparse fault-tolerant reachability preservers, resilient to two or more failures. Prior to this work, such oracles and reachability preservers were widely studied for the special scenario of single-source and all-pairs settings. However, for the scenario of arbitrary pairs, no prior (non-trivial) results were known for dual (or more) failures, except those implied from the single-source setting. One of the main questions is whether it is possible to beat the $O(n |P|)$ size bound (derived from the single-source setting) for reachability oracle and preserver for dual failures (or $O(2^k n|P|)$ bound for $k$ failures). We answer this question affirmatively. △ Less

Submitted 22 October, 2021; originally announced October 2021.

MSC Class: 68P05; 05C85 ACM Class: E.1

Uncertainty Prediction for Machine Learning Models of Material Properties

Authors: Francesca Tavazza, Brian De Cost, Kamal Choudhary

Abstract: Uncertainty quantification in Artificial Intelligence (AI)-based predictions of material properties is of immense importance for the success and reliability of AI applications in material science. While confidence intervals are commonly reported for machine learning (ML) models, prediction intervals, i.e., the evaluation of the uncertainty on each prediction, are seldomly available. In this work w… ▽ More Uncertainty quantification in Artificial Intelligence (AI)-based predictions of material properties is of immense importance for the success and reliability of AI applications in material science. While confidence intervals are commonly reported for machine learning (ML) models, prediction intervals, i.e., the evaluation of the uncertainty on each prediction, are seldomly available. In this work we compare 3 different approaches to obtain such individual uncertainty, testing them on 12 ML-physical properties. Specifically, we investigated using the Quantile loss function, machine learning the prediction intervals directly and using Gaussian Processes. We identify each approachs advantages and disadvantages and end up slightly favoring the modeling of the individual uncertainties directly, as it is the easiest to fit and, in most cases, minimizes over-and under-estimation of the predicted errors. All data for training and testing were taken from the publicly available JARVIS-DFT database, and the codes developed for computing the prediction intervals are available through JARVIS-Tools. △ Less

Submitted 16 July, 2021; originally announced July 2021.

Budgeted Dominating Sets in Uncertain Graphs

Authors: Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, R. Vijayaragunathan

Abstract: We study the {\em Budgeted Dominating Set} (BDS) problem on uncertain graphs, namely, graphs with a probability distribution $p$ associated with the edges, such that an edge $e$ exists in the graph with probability $p(e)$. The input to the problem consists of a vertex-weighted uncertain graph $\G=(V, E, p, ω)$ and an integer {\em budget} (or {\em solution size}) $k$, and the objective is to comput… ▽ More We study the {\em Budgeted Dominating Set} (BDS) problem on uncertain graphs, namely, graphs with a probability distribution $p$ associated with the edges, such that an edge $e$ exists in the graph with probability $p(e)$. The input to the problem consists of a vertex-weighted uncertain graph $\G=(V, E, p, ω)$ and an integer {\em budget} (or {\em solution size}) $k$, and the objective is to compute a vertex set $S$ of size $k$ that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of $S$. We refer to the problem as the {\em Probabilistic Budgeted Dominating Set}~(PBDS) problem and present the following results. \begin{enumerate} \dnsitem We show that the PBDS problem is NP-complete even when restricted to uncertain {\em trees} of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is \wone-hard for the budget parameter $k$, and under the {\em Exponential time hypothesis} it cannot be solved in $n^{o(k)}$ time. \item We show that if one is willing to settle for $(1-ε)$ approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. \item We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is \wone-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget $k$ and the treewidth. \item Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. \end{enumerate} △ Less

Submitted 7 July, 2021; originally announced July 2021.

Creating and Implementing a Smart Speaker

Authors: Sanskar Jethi, Avinash Kumar Choudhary, Yash Gupta, Abhishek Chaudhary

Abstract: We have seen significant advancements in Artificial Intelligence and Machine Learning in the 21st century. It has enabled a new technology where we can have a human-like conversation with the machines. The most significant use of this speech recognition and contextual understanding technology exists in the form of a Smart Speaker. We have a wide variety of Smart Speaker products available to us. T… ▽ More We have seen significant advancements in Artificial Intelligence and Machine Learning in the 21st century. It has enabled a new technology where we can have a human-like conversation with the machines. The most significant use of this speech recognition and contextual understanding technology exists in the form of a Smart Speaker. We have a wide variety of Smart Speaker products available to us. This paper aims to decode its creation and explain the technology that makes these Speakers, "Smart." △ Less

Submitted 30 May, 2021; originally announced June 2021.

Journal ref: IT in Industry, Vol. 9, No.3, 2021

New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures

Authors: Diptarka Chakraborty, Keerti Choudhary

Abstract: In this paper, we consider the question of computing sparse subgraphs for any input directed graph $G=(V,E)$ on $n$ vertices and $m$ edges, that preserves reachability and/or strong connectivity structures. We show $O(n+\min\{|{\cal P}|\sqrt{n},n\sqrt{|{\cal P}|}\})$ bound on a subgraph that is an $1$-fault-tolerant reachability preserver for a given vertex-pair set… ▽ More In this paper, we consider the question of computing sparse subgraphs for any input directed graph $G=(V,E)$ on $n$ vertices and $m$ edges, that preserves reachability and/or strong connectivity structures. We show $O(n+\min\{|{\cal P}|\sqrt{n},n\sqrt{|{\cal P}|}\})$ bound on a subgraph that is an $1$-fault-tolerant reachability preserver for a given vertex-pair set ${\cal P}\subseteq V\times V$, i.e., it preserves reachability between any pair of vertices in ${\cal P}$ under single edge (or vertex) failure. Our result is a significant improvement over the previous best $O(n |{\cal P}|)$ bound obtained as a corollary of single-source reachability preserver construction. We prove our upper bound by exploiting the special structure of single fault-tolerant reachability preserver for any pair, and then considering the interaction among such structures for different pairs. In the lower bound side, we show that a 2-fault-tolerant reachability preserver for a vertex-pair set ${\cal P}\subseteq V\times V$ of size $Ω(n^ε)$, for even any arbitrarily small $ε$, requires at least $Ω(n^{1+ε/8})$ edges. This refutes the existence of linear-sized dual fault-tolerant preservers for reachability for any polynomial sized vertex-pair set. We also present the first sub-quadratic bound of at most $\tilde{O}(k 2^k n^{2-1/k})$ size, for strong-connectivity preservers of directed graphs under $k$ failures. To the best of our knowledge no non-trivial bound for this problem was known before, for a general $k$. We get our result by adopting the color-coding technique of Alon, Yuster, and Zwick [JACM'95]. △ Less

Submitted 27 April, 2020; originally announced April 2020.

Distributed Graph Realizations

Authors: John Augustine, Keerti Choudhary, Avi Cohen, David Peleg, Sumathi Sivasubramaniam, Suman Sourav

Abstract: We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization both of which result in overlay network realizations. Overlay network realizati… ▽ More We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization both of which result in overlay network realizations. Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge. The main realization algorithms we present are the following. 1. An $\tilde{O}(\min\{\sqrt{m},Δ\})$ time algorithm for implicit realization of a degree sequence. Here, $Δ= \max_v d(v)$ is the maximum degree and $m = (1/2) \sum_v d(v)$ is the number of edges in the final realization. An $\tilde{O}(Δ)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde{O}(Δ)$ additional rounds. 2. An $\tilde{O}(Δ)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{O}(1)$ algorithm for implicit realization when all nodes know each other's IDs. These algorithms are 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$. Additionally, we provide algorithms for realizing trees and an $\tilde{O}(1)$ round algorithm for approximate degree sequence realization. △ Less

Submitted 18 February, 2021; v1 submitted 13 February, 2020; originally announced February 2020.

Comments: 22 pages, 4 figures. Short version to appear in IPDPS 2020

Efficiently Realizing Interval Sequences

Authors: Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz

Abstract: We consider the problem of realizable interval-sequences. An interval sequence comprises of $n$ integer intervals $[a_i,b_i]$ such that $0\leq a_i \leq b_i \leq n-1$, and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n)$ satisfying the condition $a_i \leq d_i \leq b_i$, for each $i \in [1,n]$. There is a characterisation (also implying an… ▽ More We consider the problem of realizable interval-sequences. An interval sequence comprises of $n$ integer intervals $[a_i,b_i]$ such that $0\leq a_i \leq b_i \leq n-1$, and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n)$ satisfying the condition $a_i \leq d_i \leq b_i$, for each $i \in [1,n]$. There is a characterisation (also implying an $O(n)$ verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdos-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length $p$ non-graphic sequence to a graphic one. △ Less

Submitted 31 December, 2019; originally announced December 2019.

Comments: 19 pages, 1 figure

Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods

Authors: Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz

Abstract: The classical problem of degree sequence realizability asks whether or not a given sequence of $n$ positive integers is equal to the degree sequence of some $n$-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information pro… ▽ More The classical problem of degree sequence realizability asks whether or not a given sequence of $n$ positive integers is equal to the degree sequence of some $n$-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper, we initiate the study of neighborhood degree profiles. We focus on the natural problem of realizing maximum and minimum neighborhood degrees. More specifically, we ask the following question: Given a sequence $D$ of $n$ non-negative integers $0\leq d_1\leq \cdots \leq d_n$, does there exist a simple graph with vertices $v_1,\ldots, v_n$ such that for every $1\le i \le n$, the maximum (resp. minimum) degree in the neighborhood of $v_i$ is exactly $d_i$? We provide in this work various results for both maximum as well as minimum neighborhood degree for general $n$ vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For maximum neighborhood degree profiles, we provide a {\em complete realizability criteria}. In comparison, we observe that the minimum neighborhood profiles are not so well-behaved, for these our necessary and sufficient conditions for realizability {\em differ by a factor of at most two}. △ Less

Submitted 31 December, 2019; originally announced December 2019.

Comments: 26 pages, 4 figures

Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances

Authors: Keerti Choudhary, Omer Gold

Abstract: The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread throughout data and communication networks. Thus, it is a natural question to ask how much can we sparsify a graph and still guarantee that its diameter remains preserved within an approximation $t$. This property is captur… ▽ More The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread throughout data and communication networks. Thus, it is a natural question to ask how much can we sparsify a graph and still guarantee that its diameter remains preserved within an approximation $t$. This property is captured by the notion of extremal-distance spanners. Given a graph $G=(V,E)$, a subgraph $H=(V,E_H)$ is defined to be a $t$-diameter spanner if the diameter of $H$ is at most $t$ times the diameter of $G$. We show that for any $n$-vertex and $m$-edges directed graph $G$, we can compute a sparse subgraph $H$ that is a $(1.5)$-diameter spanner of $G$, such that $H$ contains at most $\tilde O(n^{1.5})$ edges. We also show that the stretch factor cannot be improved to $(1.5-ε)$. For a graph whose diameter is bounded by some constant, we show the existence of $\frac{5}{3}$-diameter spanner that contains at most $\tilde O(n^\frac{4}{3})$ edges. We also show that this bound is tight. Additionally, we present other types of extremal-distance spanners, such as $2$-eccentricity spanners and $2$-radius spanners, both contain only $\tilde O(n)$ edges and are computable in $\tilde O(m)$ time. Finally, we study extremal-distance spanners in the dynamic and fault-tolerant settings. An interesting implication of our work is the first $\tilde O(m)$-time algorithm for computing $2$-approximation of vertex eccentricities in general directed weighted graphs. Backurs et al. [STOC 2018] gave an $\tilde O(m\sqrt{n})$ time algorithm for this problem, and also showed that no $O(n^{2-o(1)})$ time algorithm can achieve an approximation factor better than $2$ for graph eccentricities, unless SETH fails; this shows that our approximation factor is essentially tight. △ Less

Submitted 20 February, 2019; v1 submitted 4 December, 2018; originally announced December 2018.

Comments: 25 pages

An efficient strongly connected components algorithm in the fault tolerant model

Authors: Surender Baswana, Keerti Choudhary, Liam Roditty

Abstract: In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value $k\geq 1$, there is an algorithm that computes in $O(2^{k}n\log^2 n)$ time for any set $F$ of size at most $k$ the strongly connected components of the graph… ▽ More In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value $k\geq 1$, there is an algorithm that computes in $O(2^{k}n\log^2 n)$ time for any set $F$ of size at most $k$ the strongly connected components of the graph $G\setminus F$. The running time of our algorithm is almost optimal since the time for outputting the SCCs of $G\setminus F$ is at least $Ω(n)$. The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size $O(2^{k} n^2)$. Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest. △ Less

Submitted 24 April, 2017; v1 submitted 13 October, 2016; originally announced October 2016.

Comments: 16 pages, 2 figures

Dynamic DFS Tree in Undirected Graphs: breaking the $O(m)$ barrier

Authors: Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan

Abstract: Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing {\em updates} (insertion and deletion of vertices or edges). We present the following… ▽ More Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing {\em updates} (insertion and deletion of vertices or edges). We present the following results for this problem. (a) Fault tolerant DFS tree: There exists a data structure of size ${O}(m ~polylog~ n)$ such that given any set ${\cal F}$ of failed vertices or edges, a DFS tree of the graph $G\setminus {\cal F}$ can be reported in ${O}(n|{\cal F}| ~polylog~ n)$ time. (b) Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case ${O}(\sqrt{mn} ~polylog~ n)$ time per update for any arbitrary online sequence of updates. (c) Incremental DFS tree: Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in ${O}(n ~polylog~ n)$ worst case time per edge insertion. These are the first $o(m)$ worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm with $O(1)$ query time and $o(m)$ worst case update time for the dynamic subgraph connectivity, biconnectivity, and 2-edge connectivity. △ Less

Submitted 7 February, 2018; v1 submitted 9 February, 2015; originally announced February 2015.

Comments: 27 pages, SODA 2016

Impact of Internet Governance

Authors: Saraswati Mishra, Shikha Dhankar, Kavita Choudhary

Abstract: This paper represents the overview of the influence of internet governance in all the transactions, trading, business, social services, educational activities, research etc. occurring through the internet. It is very essential to implement laws and regulations in the field wherever the transaction takes place, either in the form of money, material or services. To avoid any kind of fraud and cheati… ▽ More This paper represents the overview of the influence of internet governance in all the transactions, trading, business, social services, educational activities, research etc. occurring through the internet. It is very essential to implement laws and regulations in the field wherever the transaction takes place, either in the form of money, material or services. To avoid any kind of fraud and cheating and to establish a peaceful environment in physical as well as virtual word, it is essential to have some organization which assures safety and security. Here I-governance is the governing body that tries to take care of all those requirements. △ Less

Submitted 12 June, 2014; originally announced June 2014.

Comments: 4 pages, 2 figures, Internation Journal of Computer Trends and Technology- IJCTT, Vol 4, Issue 10,October 2013

Classification of Flames in Computer Mediated Communications

Authors: Nitin, Ankush Bansal, Siddhartha Mahadev Sharma, Kapil Kumar, Anuj Aggarwal, Sheenu Goyal, Kanika Choudhary, Kunal Chawla, Kunal Jain, Manav Bhasin

Abstract: Computer Mediated Communication (CMC) has brought about a revolution in the way the world communicates with each other. With the increasing number of people, interacting through the internet and the rise of new platforms and technologies has brought together the people from different social, cultural and geographical backgrounds to present their thoughts, ideas and opinions on topics of their inte… ▽ More Computer Mediated Communication (CMC) has brought about a revolution in the way the world communicates with each other. With the increasing number of people, interacting through the internet and the rise of new platforms and technologies has brought together the people from different social, cultural and geographical backgrounds to present their thoughts, ideas and opinions on topics of their interest. CMC has, in some cases, gave users more freedom to express themselves as compared to Face-to-face communication. This has also led to rise in the use of hostile and aggressive language and terminologies uninhibitedly. Since such use of language is detrimental to the discussion process and affects the audience and individuals negatively, efforts are being taken to control them. The research sees the need to understand the concept of flaming and hence attempts to classify them in order to give a better understanding of it. The classification is done on the basis of type of flame content being presented and the Style in which they are presented. △ Less

Submitted 17 February, 2012; v1 submitted 3 February, 2012; originally announced February 2012.

Comments: 6 pages, 4 figures

Report number: pxc3872505

Journal ref: International Journal of Computer Applications (0975-8887), Volume 14 - No.6, February 2011

A Note on Total and Paired Domination of Cartesian Product Graphs

Authors: K. Choudhary, S. Margulies, I. V. Hicks

Abstract: A dominating set $D$ for a graph $G$ is a subset of $V(G)$ such that any vertex not in $D$ has at least one neighbor in $D$. The domination number $γ(G)$ is the size of a minimum dominating set in $G$. Vizing's conjecture from 1968 states that for the Cartesian product of graphs $G$ and $H$, $γ(G) γ(H) \leq γ(G \Box H)$, and Clark and Suen (2000) proved that $γ(G) γ(H) \leq 2γ(G \Box H)$. In this… ▽ More A dominating set $D$ for a graph $G$ is a subset of $V(G)$ such that any vertex not in $D$ has at least one neighbor in $D$. The domination number $γ(G)$ is the size of a minimum dominating set in $G$. Vizing's conjecture from 1968 states that for the Cartesian product of graphs $G$ and $H$, $γ(G) γ(H) \leq γ(G \Box H)$, and Clark and Suen (2000) proved that $γ(G) γ(H) \leq 2γ(G \Box H)$. In this paper, we modify the approach of Clark and Suen to prove a variety of similar bounds related to total and paired domination, and also extend these bounds to the $n$-Cartesian product of graphs $A^1$ through $A^n$. △ Less

Submitted 9 September, 2011; originally announced September 2011.

An Exploration of OpenCL for a Numerical Relativity Application

Authors: Niket K. Choudhary, Rakesh Ginjupalli, Sandeep Navada, Gaurav Khanna

Abstract: Currently there is considerable interest in making use of many-core processor architectures, such as Nvidia and AMD graphics processing units (GPUs) for scientific computing. In this work we explore the use of the Open Computing Language (OpenCL) for a typical Numerical Relativity application: a time-domain Teukolsky equation solver (a linear, hyperbolic, partial differential equation solver using… ▽ More Currently there is considerable interest in making use of many-core processor architectures, such as Nvidia and AMD graphics processing units (GPUs) for scientific computing. In this work we explore the use of the Open Computing Language (OpenCL) for a typical Numerical Relativity application: a time-domain Teukolsky equation solver (a linear, hyperbolic, partial differential equation solver using finite-differencing). OpenCL is the only vendor-agnostic and multi-platform parallel computing framework that has been adopted by all major processor vendors. Therefore, it allows us to write portable source-code and run it on a wide variety of compute hardware and perform meaningful comparisons. The outcome of our experimentation suggests that it is relatively straightforward to obtain order-of-magnitude gains in overall application performance by making use of many-core GPUs over multi-core CPUs and this fact is largely independent of the specific hardware architecture and vendor. We also observe that a single high-end GPU can match the performance of a small-sized, message-passing based CPU cluster. △ Less

Submitted 3 October, 2011; v1 submitted 19 October, 2010; originally announced October 2010.

Comments: 6 pages, 1 table; Accepted for publication in Parallel and Distributed Computing and Systems (PDCS 2011)