Showing 1–29 of 29 results for author: Sharma, E

Analysis and Optimization of RIS-Assisted Cell-Free Massive MIMO NOMA Systems

Authors: Malay Chakraborty, Ekant Sharma, Himal A. Suraweera, Hien Quoc Ngo

Abstract: We consider a reconfigurable intelligent surface (RIS) assisted cell-free massive multiple-input multiple-output non-orthogonal multiple access (NOMA) system, where each access point (AP) serves all the users with the aid of the RIS. We practically model the system by considering imperfect instantaneous channel state information (CSI) and employing imperfect successive interference cancellation at… ▽ More We consider a reconfigurable intelligent surface (RIS) assisted cell-free massive multiple-input multiple-output non-orthogonal multiple access (NOMA) system, where each access point (AP) serves all the users with the aid of the RIS. We practically model the system by considering imperfect instantaneous channel state information (CSI) and employing imperfect successive interference cancellation at the users end. We first obtain the channel estimates using linear minimum mean square error approach considering the spatial correlation at the RIS and then derive a closed-form downlink spectral efficiency (SE) expression using the statistical CSI. We next formulate a joint optimization problem to maximize the sum SE of the system. We first introduce a novel successive Quadratic Transform (successive-QT) algorithm to optimize the transmit power coefficients using the concept of block optimization along with quadratic transform and then use the particle swarm optimization technique to design the RIS phase shifts. Note that most of the existing works on RIS-aided cell-free systems are specific instances of the general scenario studied in this work. We numerically show that i) the RIS-assisted link is more advantageous at lower transmit power regions where the direct link between AP and user is weak, ii) NOMA outperforms orthogonal multiple access schemes in terms of SE, and iii) the proposed joint optimization framework significantly improves the sum SE of the system. △ Less

Submitted 4 July, 2024; originally announced July 2024.

Simultaneous linear connectivity of neural networks modulo permutation

Authors: Ekansh Sharma, Devin Kwok, Tom Denton, Daniel M. Roy, David Rolnick, Gintare Karolina Dziugaite

Abstract: Neural networks typically exhibit permutation symmetries which contribute to the non-convexity of the networks' loss landscapes, since linearly interpolating between two permuted versions of a trained network tends to encounter a high loss barrier. Recent work has argued that permutation symmetries are the only sources of non-convexity, meaning there are essentially no such barriers between traine… ▽ More Neural networks typically exhibit permutation symmetries which contribute to the non-convexity of the networks' loss landscapes, since linearly interpolating between two permuted versions of a trained network tends to encounter a high loss barrier. Recent work has argued that permutation symmetries are the only sources of non-convexity, meaning there are essentially no such barriers between trained networks if they are permuted appropriately. In this work, we refine these arguments into three distinct claims of increasing strength. We show that existing evidence only supports "weak linear connectivity"-that for each pair of networks belonging to a set of SGD solutions, there exist (multiple) permutations that linearly connect it with the other networks. In contrast, the claim "strong linear connectivity"-that for each network, there exists one permutation that simultaneously connects it with the other networks-is both intuitively and practically more desirable. This stronger claim would imply that the loss landscape is convex after accounting for permutation, and enable linear interpolation between three or more independently trained models without increased loss. In this work, we introduce an intermediate claim-that for certain sequences of networks, there exists one permutation that simultaneously aligns matching pairs of networks from these sequences. Specifically, we discover that a single permutation aligns sequences of iteratively trained as well as iteratively pruned networks, meaning that two networks exhibit low loss barriers at each step of their optimization and sparsification trajectories respectively. Finally, we provide the first evidence that strong linear connectivity may be possible under certain conditions, by showing that barriers decrease with increasing network width when interpolating among three networks. △ Less

Submitted 9 April, 2024; originally announced April 2024.

Comments: 11 pages, 6 figures

Can LLMs Compute with Reasons?

Authors: Harshit Sandilya, Peehu Raj, Jainit Sushil Bafna, Srija Mukhopadhyay, Shivansh Sharma, Ellwil Sharma, Arastu Sharma, Neeta Trivedi, Manish Shrivastava, Rajesh Kumar

Abstract: Large language models (LLMs) often struggle with complex mathematical tasks, prone to "hallucinating" incorrect answers due to their reliance on statistical patterns. This limitation is further amplified in average Small LangSLMs with limited context and training data. To address this challenge, we propose an "Inductive Learning" approach utilizing a distributed network of SLMs. This network lever… ▽ More Large language models (LLMs) often struggle with complex mathematical tasks, prone to "hallucinating" incorrect answers due to their reliance on statistical patterns. This limitation is further amplified in average Small LangSLMs with limited context and training data. To address this challenge, we propose an "Inductive Learning" approach utilizing a distributed network of SLMs. This network leverages error-based learning and hint incorporation to refine the reasoning capabilities of SLMs. Our goal is to provide a framework that empowers SLMs to approach the level of logic-based applications achieved by high-parameter models, potentially benefiting any language model. Ultimately, this novel concept paves the way for bridging the logical gap between humans and LLMs across various fields. △ Less

Submitted 19 February, 2024; originally announced February 2024.

Comments: 8 pages

MSC Class: 68T50 ACM Class: I.2.7

Nash Equilibria of Two-Player Matrix Games Repeated Until Collision

Authors: Aniket Murhekar, Eklavya Sharma

Abstract: We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously pick an action from a common action set $\{1, 2, \dots, n\}$. Depending on their chosen actions, they derive payoffs given by $n \times n$ matrices $A$ and $B$, respectively. If their actions collide (i.e., they pick the… ▽ More We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously pick an action from a common action set $\{1, 2, \dots, n\}$. Depending on their chosen actions, they derive payoffs given by $n \times n$ matrices $A$ and $B$, respectively. If their actions collide (i.e., they pick the same action), the game ends, otherwise, it proceeds to the next round. Both players want to maximize their total payoff until the game ends. RUC games can be interpreted as pursuit-evasion games or repeated hide-and-seek games. They also generalize hand cricket, a popular game among children in India. We show that under mild assumptions on the payoff matrices, every RUC game admits a Nash equilibrium (NE). Moreover, we show the existence of a stationary NE, where each player chooses their action according to a probability distribution over the action set that does not change across rounds. Remarkably, we show that all NE are effectively the same as the stationary NE, thus showing that RUC games admit an almost unique NE. Lastly, we also show how to compute (approximate) NE for RUC games. △ Less

Submitted 26 September, 2023; originally announced September 2023.

Comments: Accepted to FSTTCS 2023

Improving Approximation Guarantees for Maximin Share

Authors: Hannaneh Akrami, Jugal Garg, Eklavya Sharma, Setareh Taki

Abstract: We consider fair division of a set of indivisible goods among $n$ agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her ($1$-out-of-$n$) MMS value. An allocation is called MMS if all agents receive their MMS values. However, since MMS al… ▽ More We consider fair division of a set of indivisible goods among $n$ agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her ($1$-out-of-$n$) MMS value. An allocation is called MMS if all agents receive their MMS values. However, since MMS allocations do not always exist, the focus shifted to investigating its ordinal and multiplicative approximations. In the ordinal approximation, the goal is to show the existence of $1$-out-of-$d$ MMS allocations (for the smallest possible $d>n$). A series of works led to the state-of-the-art factor of $d=\lfloor3n/2\rfloor$ [Hosseini et al.'21]. We show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always exist, thereby improving the state-of-the-art of ordinal approximation. In the multiplicative approximation, the goal is to show the existence of $α$-MMS allocations (for the largest possible $α< 1$), which guarantees each agent at least $α$ times her MMS value. We introduce a general framework of "approximate MMS with agent priority ranking". An allocation is said to be $T$-MMS, for a non-increasing sequence $T = (τ_1, \ldots, τ_n)$ of numbers, if the agent at rank $i$ in the order gets a bundle of value at least $τ_i$ times her MMS value. This framework captures both ordinal approximation and multiplicative approximation as special cases. We show the existence of $T$-MMS allocations where $τ_i \ge \max(\frac{3}{4} + \frac{1}{12n}, \frac{2n}{2n+i-1})$ for all $i$. Furthermore, we can get allocations that are $(\frac{3}{4} + \frac{1}{12n})$-MMS ex-post and $(0.8253 + \frac{1}{36n})$-MMS ex-ante. We also prove that our algorithm does not give better than $(0.8631 + \frac{1}{2n})$-MMS ex-ante. △ Less

Submitted 16 February, 2024; v1 submitted 24 July, 2023; originally announced July 2023.

Adaptive Compliant Robot Control with Failure Recovery for Object Press-Fitting

Authors: Ekansh Sharma, Christoph Henke, Alex Mitrevski, Paul G. Plöger

Abstract: Loading of shipping containers for dairy products often includes a press-fit task, which involves manually stacking milk cartons in a container without using pallets or packaging. Automating this task with a mobile manipulator can reduce worker strain, and also enhance the efficiency and safety of the container loading process. This paper proposes an approach called Adaptive Compliant Control with… ▽ More Loading of shipping containers for dairy products often includes a press-fit task, which involves manually stacking milk cartons in a container without using pallets or packaging. Automating this task with a mobile manipulator can reduce worker strain, and also enhance the efficiency and safety of the container loading process. This paper proposes an approach called Adaptive Compliant Control with Integrated Failure Recovery (ACCIFR), which enables a mobile manipulator to reliably perform the press-fit task. We base the approach on a demonstration learning-based compliant control framework, such that we integrate a monitoring and failure recovery mechanism for successful task execution. Concretely, we monitor the execution through distance and force feedback, detect collisions while the robot is performing the press-fit task, and use wrench measurements to classify the direction of collision; this information informs the subsequent recovery process. We evaluate the method on a miniature container setup, considering variations in the (i) starting position of the end effector, (ii) goal configuration, and (iii) object grasping position. The results demonstrate that the proposed approach outperforms the baseline demonstration-based learning framework regarding adaptability to environmental variations and the ability to recover from collision failures, making it a promising solution for practical press-fit applications. △ Less

Submitted 17 July, 2023; originally announced July 2023.

Comments: Accepted for publication at the 11th European Conference on Mobile Robots (ECMR 2023)

Simplification and Improvement of MMS Approximation

Authors: Hannaneh Akrami, Jugal Garg, Eklavya Sharma, Setareh Taki

Abstract: We consider the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The Garg-Taki algorithm gives the current best approximation factor of… ▽ More We consider the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The Garg-Taki algorithm gives the current best approximation factor of $(\frac{3}{4} + \frac{1}{12n})$. Most of these results are based on complicated analyses, especially those providing better than $2/3$ factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of $(\frac{3}{4} + \min(\frac{1}{36}, \frac{3}{16n-4}))$. For small $n$, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques. △ Less

Submitted 21 July, 2023; v1 submitted 29 March, 2023; originally announced March 2023.

Smart Speech Segmentation using Acousto-Linguistic Features with look-ahead

Authors: Piyush Behre, Naveen Parihar, Sharman Tan, Amy Shah, Eva Sharma, Geoffrey Liu, Shuangyu Chang, Hosam Khalil, Chris Basoglu, Sayan Pathak

Abstract: Segmentation for continuous Automatic Speech Recognition (ASR) has traditionally used silence timeouts or voice activity detectors (VADs), which are both limited to acoustic features. This segmentation is often overly aggressive, given that people naturally pause to think as they speak. Consequently, segmentation happens mid-sentence, hindering both punctuation and downstream tasks like machine tr… ▽ More Segmentation for continuous Automatic Speech Recognition (ASR) has traditionally used silence timeouts or voice activity detectors (VADs), which are both limited to acoustic features. This segmentation is often overly aggressive, given that people naturally pause to think as they speak. Consequently, segmentation happens mid-sentence, hindering both punctuation and downstream tasks like machine translation for which high-quality segmentation is critical. Model-based segmentation methods that leverage acoustic features are powerful, but without an understanding of the language itself, these approaches are limited. We present a hybrid approach that leverages both acoustic and language information to improve segmentation. Furthermore, we show that including one word as a look-ahead boosts segmentation quality. On average, our models improve segmentation-F0.5 score by 9.8% over baseline. We show that this approach works for multiple languages. For the downstream task of machine translation, it improves the translation BLEU score by an average of 1.05 points. △ Less

Submitted 27 October, 2022; v1 submitted 25 October, 2022; originally announced October 2022.

Existence and Computation of Epistemic EFX Allocations

Authors: Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, Giovanna Varricchio

Abstract: We consider the problem of allocating indivisible goods among $n$ agents in a fair manner. For this problem, one of the best notions of fairness is envy-freeness up to any good (EFX). However, it is not known if EFX allocations always exist. Hence, several relaxations of EFX allocations have been studied. We propose another relaxation of EFX, called epistemic EFX (EEFX). An allocation is EEFX iff… ▽ More We consider the problem of allocating indivisible goods among $n$ agents in a fair manner. For this problem, one of the best notions of fairness is envy-freeness up to any good (EFX). However, it is not known if EFX allocations always exist. Hence, several relaxations of EFX allocations have been studied. We propose another relaxation of EFX, called epistemic EFX (EEFX). An allocation is EEFX iff for every agent $i$, it is possible to shuffle the goods of the other agents such that agent $i$ does not envy any other agent up to any good. We show that EEFX allocations always exist for additive valuations, and give a polynomial-time algorithm for computing them. We also show how EEFX is related to some previously-known notions of fairness. △ Less

Submitted 4 November, 2022; v1 submitted 3 June, 2022; originally announced June 2022.

Comments: Edit: include additional authors and some minor changes

Automated Application Processing

Authors: Eshita Sharma, Keshav Gupta, Lubaina Machinewala, Samaksh Dhingra, Shrey Tripathi, Shreyas V S, Sujit Kumar Chakrabarti

Abstract: Recruitment in large organisations often involves interviewing a large number of candidates. The process is resource intensive and complex. Therefore, it is important to carry it out efficiently and effectively. Planning the selection process consists of several problems, each of which maps to one or the other well-known computing problem. Research that looks at each of these problems in isolation… ▽ More Recruitment in large organisations often involves interviewing a large number of candidates. The process is resource intensive and complex. Therefore, it is important to carry it out efficiently and effectively. Planning the selection process consists of several problems, each of which maps to one or the other well-known computing problem. Research that looks at each of these problems in isolation is rich and mature. However, research that takes an integrated view of the problem is not common. In this paper, we take two of the most important aspects of the application processing problem, namely review/interview panel creation and interview scheduling. We have implemented our approach as a prototype system and have used it to automatically plan the interview process of a real-life data set. Our system provides a distinctly better plan than the existing practice, which is predominantly manual. We have explored various algorithmic options and have customised them to solve these panel creation and interview scheduling problems. We have evaluated these design options experimentally on a real data set and have presented our observations. Our prototype and experimental process and results may be a very good starting point for a full-fledged development project for automating application processing process. △ Less

Submitted 19 April, 2022; originally announced April 2022.

Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing

Authors: Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas

Abstract: We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given $n$ rectangular items where the $i^{\textrm{th}}$ item has width $w(i)$, height $h(i)$, and $d$ nonnegative weights $v_1(i), v_2(i), \ldots, v_{d}(i)$. Our goal is to get an axis-parallel non-overlapping packing of the items into square bins so that fo… ▽ More We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given $n$ rectangular items where the $i^{\textrm{th}}$ item has width $w(i)$, height $h(i)$, and $d$ nonnegative weights $v_1(i), v_2(i), \ldots, v_{d}(i)$. Our goal is to get an axis-parallel non-overlapping packing of the items into square bins so that for all $j \in [d]$, the sum of the $j^{\textrm{th}}$ weight of items in each bin is at most 1. This is a natural problem arising in logistics, resource allocation, and scheduling. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios $6(d+1)$ and $3(1 + \ln(d+1) + \varepsilon)$. We then extend the Round-and-Approx (R&A) framework [Bansal-Khan, SODA'14] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain better approximation algorithms for GVBP, and we get further improvement by combining them with the R&A framework. This gives us an asymptotic approximation ratio of $2(1+\ln((d+4)/2))+\varepsilon$ for GVBP, which improves to $2.919+\varepsilon$ for the special case of $d=1$. We obtain further improvement when the items are allowed to be rotated. We also present algorithms for a generalization of GVBP where the items are high dimensional cuboids. △ Less

Submitted 26 June, 2021; originally announced June 2021.

A review on physical and data-driven based nowcasting methods using sky images

Authors: Ekanki Sharma, Wilfried Elmenreich

Abstract: Amongst all the renewable energy resources (RES), solar is the most popular form of energy source and is of particular interest for its widely integration into the power grid. However, due to the intermittent nature of solar source, it is of the greatest significance to forecast solar irradiance to ensure uninterrupted and reliable power supply to serve the energy demand. There are several approac… ▽ More Amongst all the renewable energy resources (RES), solar is the most popular form of energy source and is of particular interest for its widely integration into the power grid. However, due to the intermittent nature of solar source, it is of the greatest significance to forecast solar irradiance to ensure uninterrupted and reliable power supply to serve the energy demand. There are several approaches to perform solar irradiance forecasting, for instance satellite-based methods, sky image-based methods, machine learning-based methods, and numerical weather prediction-based methods. In this paper, we present a review on short-term intra-hour solar prediction techniques known as nowcasting methods using sky images. Along with this, we also report and discuss which sky image features are significant for the nowcasting methods. △ Less

Submitted 28 April, 2021; originally announced May 2021.

Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items

Authors: Arindam Khan, Eklavya Sharma

Abstract: In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is $1.406$ by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillo… ▽ More In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is $1.406$ by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let $λ$ be the smallest constant such that for every set $I$ of items, the number of bins in the optimal solution to G2BP for $I$ is upper bounded by $λ\operatorname{opt}(I) + c$, where $\operatorname{opt}(I)$ is the number of bins in the optimal solution to 2BP for $I$ and $c$ is a constant. It is known that $4/3 \le λ\le 1.692$. Bansal and Khan [SODA'14] conjectured that $λ= 4/3$. The conjecture, if true, will imply a $(4/3+\varepsilon)$-approximation algorithm for 2BP. According to convention, for a given constant $δ>0$, a rectangle is large if both its height and width are at least $δ$, and otherwise it is called skewed. We make progress towards the conjecture by showing $λ= 4/3$ for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on $λ$ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS. △ Less

Submitted 6 May, 2021; originally announced May 2021.

Approximation Algorithms for Generalized Multidimensional Knapsack

Authors: Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas

Abstract: We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and $d$ nonnegative weights ($d$-dimensional vector), and a square knapsack. The goal is to find a non-overlapping axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e.,… ▽ More We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and $d$ nonnegative weights ($d$-dimensional vector), and a square knapsack. The goal is to find a non-overlapping axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the $d$ dimensions does not exceed one. We consider two variants of the problem: $(i)$ the items are not allowed to be rotated, $(ii)$ items can be rotated by 90 degrees. We give a $(2+ε)$-approximation algorithm for this problem (both versions). In the process, we also study a variant of the maximum generalized assignment problem (Max-GAP), called Vector-Max-GAP, and design a PTAS for it. △ Less

Submitted 11 February, 2021; originally announced February 2021.

Analysis of the Harmonic Function Used in Bin-Packing

Authors: Eklavya Sharma

Abstract: The harmonic function was first introduced by Lee and Lee (JACM 1985) for analyzing their online bin-packing algorithm. Subsequently, it has been used to obtain approximation algorithms for many different packing problems. Here we slightly generalize the harmonic function and give alternative proofs of its important properties. The harmonic function was first introduced by Lee and Lee (JACM 1985) for analyzing their online bin-packing algorithm. Subsequently, it has been used to obtain approximation algorithms for many different packing problems. Here we slightly generalize the harmonic function and give alternative proofs of its important properties. △ Less

Submitted 17 December, 2020; v1 submitted 23 November, 2020; originally announced November 2020.

Comments: Update: fixed typo and added acknowledgements

An Approximation Algorithm for Covering Linear Programs and its Application to Bin-Packing

Authors: Eklavya Sharma

Abstract: We give an $α(1+ε)$-approximation algorithm for solving covering LPs, assuming the presence of a $(1/α)$-approximation algorithm for a certain optimization problem. Our algorithm is based on a simple modification of the Plotkin-Shmoys-Tardos algorithm (MOR 1995). We then apply our algorithm to $α(1+ε)$-approximately solve the configuration LP for a large class of bin-packing problems, assuming the… ▽ More We give an $α(1+ε)$-approximation algorithm for solving covering LPs, assuming the presence of a $(1/α)$-approximation algorithm for a certain optimization problem. Our algorithm is based on a simple modification of the Plotkin-Shmoys-Tardos algorithm (MOR 1995). We then apply our algorithm to $α(1+ε)$-approximately solve the configuration LP for a large class of bin-packing problems, assuming the presence of a $(1/α)$-approximate algorithm for the corresponding knapsack problem (KS). Previous results give us a PTAS for the configuration LP using a PTAS for KS. Those results don't extend to the case where KS is poorly approximated. Our algorithm, however, works even for polynomially-large $α$. △ Less

Submitted 17 December, 2020; v1 submitted 23 November, 2020; originally announced November 2020.

Comments: Update: added acknowledgements

Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins

Authors: Eklavya Sharma

Abstract: We explore approximation algorithms for the $d$-dimensional geometric bin packing problem ($d$BP). Caprara (MOR 2008) gave a harmonic-based algorithm for $d$BP having an asymptotic approximation ratio (AAR) of $T_{\infty}^{d-1}$ (where $T_{\infty} \approx 1.691$). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of $d$BP, like packing boxe… ▽ More We explore approximation algorithms for the $d$-dimensional geometric bin packing problem ($d$BP). Caprara (MOR 2008) gave a harmonic-based algorithm for $d$BP having an asymptotic approximation ratio (AAR) of $T_{\infty}^{d-1}$ (where $T_{\infty} \approx 1.691$). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of $d$BP, like packing boxes into shipping containers. We give approximation algorithms for $d$BP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm having AAR $T_{\infty}^{d}$. We next give a more sophisticated harmonic-based algorithm, which we call $\mathtt{HGaP}_k$, having AAR $T_{\infty}^{d-1}(1+ε)$. This gives an AAR of roughly $2.860 + ε$ for 3BP with rotations, which improves upon the best-known AAR of $4.5$. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given $n$ sets of $d$-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of $d$D strip packing and $d$D geometric knapsack. △ Less

Submitted 25 September, 2021; v1 submitted 22 November, 2020; originally announced November 2020.

Comments: Update 3: slightly improve readability, mention dependence on d; Update 2: major refactoring; Update 1: fix typos, slightly improve readability, use title-case for title

FD Cell-Free mMIMO: Analysis and Optimization

Authors: Soumyadeep Datta, Ekant Sharma, Dheeraj Naidu Amudala, Rohit Budhiraja, Shivendra S. Panwar

Abstract: Cell-free (CF) massive multiple-input-multiple-output (mMIMO) deployments are usually investigated with half-duplex nodes and high-capacity fronthaul links. To leverage the possible gains in throughput and energy efficiency (EE) of full-duplex (FD) communications, we consider a FD CF mMIMO system with practical limited-capacity fronthaul links. We derive closed-form spectral efficiency (SE) lower… ▽ More Cell-free (CF) massive multiple-input-multiple-output (mMIMO) deployments are usually investigated with half-duplex nodes and high-capacity fronthaul links. To leverage the possible gains in throughput and energy efficiency (EE) of full-duplex (FD) communications, we consider a FD CF mMIMO system with practical limited-capacity fronthaul links. We derive closed-form spectral efficiency (SE) lower bounds for this system with maximum-ratio combining/maximum-ratio transmission processing and optimal uniform quantization. We then optimize the weighted sum EE (WSEE) via downlink and uplink power control by using a {two-layered} approach: the first layer formulates the optimization as a generalized convex program, while the second layer solves the optimization decentrally using alternating direction method of multipliers. We analytically show that the proposed two-layered formulation yields a Karush-Kuhn-Tucker point of the original WSEE optimization. We numerically show the influence of weights on the individual EE of the users, which demonstrates the utility of WSEE metric to incorporate heterogeneous EE requirements of users. We show that the low fronthaul capacity reduces the number of users each AP can support, and the cell-free system, consequently, becomes user-centric. △ Less

Submitted 31 May, 2021; v1 submitted 27 October, 2020; originally announced October 2020.

Comments: Accepted in IEEE International Conference on Communications (ICC) 2021. arXiv admin note: substantial text overlap with arXiv:2010.14110

Full-Duplex Cell-Free mMIMO Systems: Analysis and Decentralized Optimization

Authors: Soumyadeep Datta, Dheeraj Naidu Amudala, Ekant Sharma, Rohit Budhiraja, Shivendra S. Panwar

Abstract: Cell-free (CF) massive multiple-input-multiple-output (mMIMO) deployments are usually investigated with half-duplex nodes and high-capacity fronthaul links. To leverage the possible gains in throughput and energy efficiency (EE) of full-duplex (FD) communications, we consider a FD CF mMIMO system with practical limited-capacity fronthaul links. We derive closed-form spectral efficiency (SE) lower… ▽ More Cell-free (CF) massive multiple-input-multiple-output (mMIMO) deployments are usually investigated with half-duplex nodes and high-capacity fronthaul links. To leverage the possible gains in throughput and energy efficiency (EE) of full-duplex (FD) communications, we consider a FD CF mMIMO system with practical limited-capacity fronthaul links. We derive closed-form spectral efficiency (SE) lower bounds for this system with maximum-ratio combining/maximum-ratio transmission processing and optimal uniform quantization. We then optimize the weighted sum EE (WSEE) via downlink and uplink power control by using a two-layered approach: the first layer formulates the optimization as a generalized convex program, while the {second layer} solves the optimization decentrally using the alternating direction method of multipliers. We analytically show that the proposed two-layered formulation yields a Karush-Kuhn-Tucker point of the original WSEE optimization. We numerically show the influence of weights on the individual EE of the users, which demonstrates the utility of the WSEE metric to incorporate heterogeneous EE requirements of users. We show that low fronthaul capacity reduces the number of users each AP can support, and the cell-free system, consequently, becomes user-centric. △ Less

Submitted 10 December, 2021; v1 submitted 27 October, 2020; originally announced October 2020.

Comments: Accepted for publication to the IEEE Open Journal of the Communications Society

Classifying Songs with EEG

Authors: Prashant Lawhatre, Bharatesh R Shiraguppi, Esha Sharma, Krishna Prasad Miyapuram, Derek Lomas

Abstract: This research study aims to use machine learning methods to characterize the EEG response to music. Specifically, we investigate how resonance in the EEG response correlates with individual aesthetic enjoyment. Inspired by the notion of musical processing as resonance, we hypothesize that the intensity of an aesthetic experience is based on the degree to which a participants EEG entrains to the pe… ▽ More This research study aims to use machine learning methods to characterize the EEG response to music. Specifically, we investigate how resonance in the EEG response correlates with individual aesthetic enjoyment. Inspired by the notion of musical processing as resonance, we hypothesize that the intensity of an aesthetic experience is based on the degree to which a participants EEG entrains to the perceptual input. To test this and other hypotheses, we have built an EEG dataset from 20 subjects listening to 12 two minute-long songs in random order. After preprocessing and feature construction, we used this dataset to train and test multiple machine learning models. △ Less

Submitted 1 October, 2020; originally announced October 2020.

Approximations in Probabilistic Programs

Authors: Ekansh Sharma, Daniel M. Roy

Abstract: We study the first-order probabilistic programming language introduced by Staton et al. (2016), but with an additional language construct, $\mathbf{stat}$, that, like the fixpoint operator of Atkinson et al. (2018), converts the description of the Markov kernel of an ergodic Markov chain into a sample from its unique stationary distribution. Up to minor changes in how certain error conditions are… ▽ More We study the first-order probabilistic programming language introduced by Staton et al. (2016), but with an additional language construct, $\mathbf{stat}$, that, like the fixpoint operator of Atkinson et al. (2018), converts the description of the Markov kernel of an ergodic Markov chain into a sample from its unique stationary distribution. Up to minor changes in how certain error conditions are handled, we show that $\mathbf{norm}$ and $\mathbf{score}$ are eliminable from the extended language, in the sense of Felleisen (1991). We do so by giving an explicit program transformation and proof of correctness. In fact, our program transformation implements a Markov chain Monte Carlo algorithm, in the spirit of the "Trace-MH" algorithm of Wingate et al. (2011) and Goodman et al. (2008), but less sophisticated to enable analysis. We then explore the problem of approximately implementing the semantics of the language with potentially nested $\mathbf{stat}$ expressions, in a language without $\mathbf{stat}$. For a single $\mathbf{stat}$ term, the error introduced by the finite unrolling proposed by Atkinson et al. (2018) vanishes only asymptotically. In the general case, no guarantees exist. Under uniform ergodicity assumptions, we are able to give quantitative error bounds and convergence results for the approximate implementation of the extended first-order language. △ Less

Submitted 14 December, 2019; originally announced December 2019.

Comments: 15 pages, 3 figures

In Plain Sight: Media Bias Through the Lens of Factual Reporting

Authors: Lisa Fan, Marshall White, Eva Sharma, Ruisi Su, Prafulla Kumar Choubey, Ruihong Huang, Lu Wang

Abstract: The increasing prevalence of political bias in news media calls for greater public awareness of it, as well as robust methods for its detection. While prior work in NLP has primarily focused on the lexical bias captured by linguistic attributes such as word choice and syntax, other types of bias stem from the actual content selected for inclusion in the text. In this work, we investigate the effec… ▽ More The increasing prevalence of political bias in news media calls for greater public awareness of it, as well as robust methods for its detection. While prior work in NLP has primarily focused on the lexical bias captured by linguistic attributes such as word choice and syntax, other types of bias stem from the actual content selected for inclusion in the text. In this work, we investigate the effects of informational bias: factual content that can nevertheless be deployed to sway reader opinion. We first produce a new dataset, BASIL, of 300 news articles annotated with 1,727 bias spans and find evidence that informational bias appears in news articles more frequently than lexical bias. We further study our annotations to observe how informational bias surfaces in news articles by different media outlets. Lastly, a baseline model for informational bias prediction is presented by fine-tuning BERT on our labeled data, indicating the challenges of the task and future directions. △ Less

Submitted 5 September, 2019; originally announced September 2019.

Comments: To appear as a short paper in EMNLP 2019

An Entity-Driven Framework for Abstractive Summarization

Authors: Eva Sharma, Luyang Huang, Zhe Hu, Lu Wang

Abstract: Abstractive summarization systems aim to produce more coherent and concise summaries than their extractive counterparts. Popular neural models have achieved impressive results for single-document summarization, yet their outputs are often incoherent and unfaithful to the input. In this paper, we introduce SENECA, a novel System for ENtity-drivEn Coherent Abstractive summarization framework that le… ▽ More Abstractive summarization systems aim to produce more coherent and concise summaries than their extractive counterparts. Popular neural models have achieved impressive results for single-document summarization, yet their outputs are often incoherent and unfaithful to the input. In this paper, we introduce SENECA, a novel System for ENtity-drivEn Coherent Abstractive summarization framework that leverages entity information to generate informative and coherent abstracts. Our framework takes a two-step approach: (1) an entity-aware content selection module first identifies salient sentences from the input, then (2) an abstract generation module conducts cross-sentence information compression and abstraction to generate the final summary, which is trained with rewards to promote coherence, conciseness, and clarity. The two components are further connected using reinforcement learning. Automatic evaluation shows that our model significantly outperforms previous state-of-the-art on ROUGE and our proposed coherence measures on New York Times and CNN/Daily Mail datasets. Human judges further rate our system summaries as more informative and coherent than those by popular summarization models. △ Less

Submitted 4 September, 2019; originally announced September 2019.

Comments: Proceedings of the 2019 Empirical Methods in Natural Language Processing Conference and 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP-2019) (19 pages)

BIGPATENT: A Large-Scale Dataset for Abstractive and Coherent Summarization

Authors: Eva Sharma, Chen Li, Lu Wang

Abstract: Most existing text summarization datasets are compiled from the news domain, where summaries have a flattened discourse structure. In such datasets, summary-worthy content often appears in the beginning of input articles. Moreover, large segments from input articles are present verbatim in their respective summaries. These issues impede the learning and evaluation of systems that can understand an… ▽ More Most existing text summarization datasets are compiled from the news domain, where summaries have a flattened discourse structure. In such datasets, summary-worthy content often appears in the beginning of input articles. Moreover, large segments from input articles are present verbatim in their respective summaries. These issues impede the learning and evaluation of systems that can understand an article's global content structure as well as produce abstractive summaries with high compression ratio. In this work, we present a novel dataset, BIGPATENT, consisting of 1.3 million records of U.S. patent documents along with human written abstractive summaries. Compared to existing summarization datasets, BIGPATENT has the following properties: i) summaries contain a richer discourse structure with more recurring entities, ii) salient content is evenly distributed in the input, and iii) lesser and shorter extractive fragments are present in the summaries. Finally, we train and evaluate baselines and popular learning models on BIGPATENT to shed light on new challenges and motivate future directions for summarization research. △ Less

Submitted 9 June, 2019; originally announced June 2019.

Comments: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. ACL 2019 (10 pages)

Impact of Artificial Intelligence on Businesses: from Research, Innovation, Market Deployment to Future Shifts in Business Models

Authors: Neha Soni, Enakshi Khular Sharma, Narotam Singh, Amita Kapoor

Abstract: The fast pace of artificial intelligence (AI) and automation is propelling strategists to reshape their business models. This is fostering the integration of AI in the business processes but the consequences of this adoption are underexplored and need attention. This paper focuses on the overall impact of AI on businesses - from research, innovation, market deployment to future shifts in business… ▽ More The fast pace of artificial intelligence (AI) and automation is propelling strategists to reshape their business models. This is fostering the integration of AI in the business processes but the consequences of this adoption are underexplored and need attention. This paper focuses on the overall impact of AI on businesses - from research, innovation, market deployment to future shifts in business models. To access this overall impact, we design a three-dimensional research model, based upon the Neo-Schumpeterian economics and its three forces viz. innovation, knowledge, and entrepreneurship. The first dimension deals with research and innovation in AI. In the second dimension, we explore the influence of AI on the global market and the strategic objectives of the businesses and finally, the third dimension examines how AI is shaping business contexts. Additionally, the paper explores AI implications on actors and its dark sides. △ Less

Submitted 3 May, 2019; originally announced May 2019.

Comments: 38 pages, 10 figures, 3 tables. A part of this work has been presented in DIGITS 2018

Hybrid Block Diagonalization for Massive MIMO Two-Way Half-Duplex AF Hybrid Relay

Authors: Arpita Singh Chauhan, Ekant Sharma, Rohit Budhiraja

Abstract: We consider a multi-pair two-way amplify-and-forward massive multi-input multi-output (MIMO) hybrid relay with MIMO user-pairs. A hybrid relay has lesser number of radio frequency (RF) chains than the antennas, which significantly reduces the implementation cost. We employ block-diagonalization-based baseband processing at the hybrid relay to cancel the inter user-pair interference and equal-gain-… ▽ More We consider a multi-pair two-way amplify-and-forward massive multi-input multi-output (MIMO) hybrid relay with MIMO user-pairs. A hybrid relay has lesser number of radio frequency (RF) chains than the antennas, which significantly reduces the implementation cost. We employ block-diagonalization-based baseband processing at the hybrid relay to cancel the inter user-pair interference and equal-gain-combining-based RF processing to maximize the beamforming gain. We also use an algebraic norm maximizing relay transmit strategy to maximize the spectral efficiency (SE) of each user-pair. We numerically show that the proposed hybrid relay has only marginally inferior SE than a full RF-chain relay. △ Less

Submitted 17 September, 2018; originally announced September 2018.

Comments: Accepted for publication in IEEE SPCOM'18

Multi-Pair Two Way AF Full-Duplex Massive MIMO Relaying with ZFR/ZFT Processing

Authors: Ekant Sharma, Rohit Budhiraja, K Vasudevan

Abstract: We consider two-way amplify and forward relaying, where multiple full-duplex user pairs exchange information via a shared full-duplex massive multiple-input multiple-output (MIMO) relay. We derive closed-form lower bound for the spectral efficiency with zero-forcing processing at the relay, by using minimum mean squared error channel estimation. The zero-forcing lower bound for the system model co… ▽ More We consider two-way amplify and forward relaying, where multiple full-duplex user pairs exchange information via a shared full-duplex massive multiple-input multiple-output (MIMO) relay. We derive closed-form lower bound for the spectral efficiency with zero-forcing processing at the relay, by using minimum mean squared error channel estimation. The zero-forcing lower bound for the system model considered herein, which is valid for arbitrary number of antennas, is not yet derived in the massive MIMO relaying literature. We numerically demonstrate the accuracy of the derived lower bound and the performance improvement achieved using zero-forcing processing. We also numerically demonstrate the spectral gains achieved by a full-duplex system over a half-duplex one for various antenna regimes. △ Less

Submitted 3 October, 2017; originally announced October 2017.

Comments: Conference paper, 6 pages

Full-Duplex Massive MIMO Multi-Pair Two-Way AF Relaying: Energy Efficiency Optimization

Authors: Ekant Sharma, Rohit Budhiraja, K Vasudevan, Lajos Hanzo

Abstract: We consider two-way amplify and forward relaying, where multiple full-duplex user pairs exchange information via a shared full-duplex massive multiple-input multiple-output (MIMO) relay. Most of the previous massive MIMO relaying works maximize the spectral efficiency (SE). By contrast, we maximize the non-convex energy efficiency (EE) metric by approximating it as a pseudo-concave problem, which… ▽ More We consider two-way amplify and forward relaying, where multiple full-duplex user pairs exchange information via a shared full-duplex massive multiple-input multiple-output (MIMO) relay. Most of the previous massive MIMO relaying works maximize the spectral efficiency (SE). By contrast, we maximize the non-convex energy efficiency (EE) metric by approximating it as a pseudo-concave problem, which is then solved using the classic Dinkelbach approach. We also maximize the EE of the least energy-efficient user {relying} on the max-min approach. For solving these optimization problems, we derive closed-form lower bounds for the ergodic achievable rate both for maximal-ratio combining and zero-forcing processing at the relay, by using minimum mean squared error channel estimation. We numerically characterize the accuracy of the lower bounds derived. We also compare the SE and EE of the proposed design to those of the existing full-duplex systems and quantify the significant improvement achieved by the proposed algorithm. We also compare the EE of the proposed full-duplex system to that of its half-duplex counterparts, and characterize the self-loop and inter-user interference regimes, for which the proposed full-duplex system succeeds in outperforming the half-duplex ones. △ Less

Submitted 4 October, 2017; v1 submitted 25 May, 2017; originally announced May 2017.

Comments: 30 pages, Updated paper

Modeling trajectories of mental health: challenges and opportunities

Authors: Lauren Erdman, Ekansh Sharma, Eva Unternahrer, Shantala Hari Dass, Kieran ODonnell, Sara Mostafavi, Rachel Edgar, Michael Kobor, Helene Gaudreau, Michael Meaney, Anna Goldenberg

Abstract: More than two thirds of mental health problems have their onset during childhood or adolescence. Identifying children at risk for mental illness later in life and predicting the type of illness is not easy. We set out to develop a platform to define subtypes of childhood social-emotional development using longitudinal, multifactorial trait-based measures. Subtypes discovered through this study cou… ▽ More More than two thirds of mental health problems have their onset during childhood or adolescence. Identifying children at risk for mental illness later in life and predicting the type of illness is not easy. We set out to develop a platform to define subtypes of childhood social-emotional development using longitudinal, multifactorial trait-based measures. Subtypes discovered through this study could ultimately advance psychiatric knowledge of the early behavioural signs of mental illness. To this extent we have examined two types of models: latent class mixture models and GP-based models. Our findings indicate that while GP models come close in accuracy of predicting future trajectories, LCMMs predict the trajectories as well in a fraction of the time. Unfortunately, neither of the models are currently accurate enough to lead to immediate clinical impact. The available data related to the development of childhood mental health is often sparse with only a few time points measured and require novel methods with improved efficiency and accuracy. △ Less

Submitted 3 December, 2016; originally announced December 2016.

Comments: extended abstract for ML4HC at NIPS 2016, 4 pages