Search

We consider the complexity of finding envy-free allocations for the class of graphical valuations. Graphical valuations were introduced by Christodoulou et. al.(2023) as a structured class of valuations that admit allocations that are envy-free up to any item (EFX). These are valuations where every item is valued by two agents, lending a (simple) graph structure to the utilities, where the agents are vertices and are adjacent if and only if they value a (unique) common item. Finding envy-free allocations for general valuations is known to be computationally intractable even for very special cases: in particular, even for binary valuations, and even for identical valuations with two agents. We show that, for binary graphical valuations, the existence of envy-free allocations can be determined in polynomial time. In contrast, we also show that allowing for even slightly more general utilities {0, 1, d} leads to intractability even for graphical valuations. This motivates other approaches to tractability, and to that end, we exhibit the fixed-parameter tractability of the problem parameterized by the vertex cover number of the graph when the number of distinct utilities is bounded. We also show that, all graphical instances that admit EF allocations also admit one that is non-wasteful. Since EFX allocations are possibly wasteful, we also address the question of determining the price of fairness of EFX allocations. We show that the price of EFX with respect to utilitarian welfare is one for binary utilities, but can be arbitrarily large {0, 1, d} valuations. We also show the hardness of deciding the existence of an EFX allocation which is also welfare-maximizing and of finding a welfare-maximizing allocation within the set of EFX allocations., Comment: 18 pages, 2 figures, 1 table. A version of this work was accepted for presentation at Algorithmic Decision Theory (ADT) 2024

Large Language Models (LLMs) have showcased impressive abilities in generating fluent responses to diverse user queries. However, concerns regarding the potential misuse of such texts in journalism, educational, and academic contexts have surfaced. SemEval 2024 introduces the task of Multigenerator, Multidomain, and Multilingual Black-Box Machine-Generated Text Detection, aiming to develop automated systems for identifying machine-generated text and detecting potential misuse. In this paper, we i) propose a RoBERTa-BiLSTM based classifier designed to classify text into two categories: AI-generated or human ii) conduct a comparative study of our model with baseline approaches to evaluate its effectiveness. This paper contributes to the advancement of automatic text detection systems in addressing the challenges posed by machine-generated text misuse. Our architecture ranked 46th on the official leaderboard with an accuracy of 80.83 among 125., Comment: SemEval-2024

We study almost-envy-freeness in house allocation, where $m$ houses are to be allocated among $n$ agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations of envy-freeness. But typical relaxations such as envy-free up to one good do not make sense for house allocation, as every agent is required to receive exactly one house. Hence we turn to different aggregate measures of envy as markers of fairness. In particular, we define the amount of envy experienced by an agent $a$ w.r.t. an allocation to be the number of agents that agent $a$ envies under that allocation. We quantify the envy generated by an allocation using three different metrics: 1) the number of agents who are envious; 2) the maximum amount of envy experienced by any agent; and 3) the total amount of envy experienced by all agents, and look for allocations that minimize one of the three metrics. We thus study three computational problems corresponding to each of the three metrics and prove a host of algorithmic and hardness results. We also suggest practical approaches for these problems via integer linear program (ILP) formulations and report the findings of our experimental evaluation of ILPs. Finally, we study the price of fairness (PoF), which quantifies the loss of welfare we must suffer due to the fairness requirements, and we prove a number of results on PoF, including tight bounds as well as algorithms that simultaneously optimize both welfare and fairness., Comment: 49 pages, 5 tables; A shorter version of this paper appeared at AAMAS 2023

With the advent of social media, fun selfie filters have come into tremendous mainstream use affecting the functioning of facial biometric systems as well as image recognition systems. These filters vary from beautification filters and Augmented Reality (AR)-based filters to filters that modify facial landmarks. Hence, there is a need to assess the impact of such filters on the performance of existing face recognition systems. The limitation associated with existing solutions is that these solutions focus more on the beautification filters. However, the current AR-based filters and filters which distort facial key points are in vogue recently and make the faces highly unrecognizable even to the naked eye. Also, the filters considered are mostly obsolete with limited variations. To mitigate these limitations, we aim to perform a holistic impact analysis of the latest filters and propose an user recognition model with the filtered images. We have utilized a benchmark dataset for baseline images, and applied the latest filters over them to generate a beautified/filtered dataset. Next, we have introduced a model FaceFilterNet for beautified user recognition. In this framework, we also utilize our model to comment on various attributes of the person including age, gender, and ethnicity. In addition, we have also presented a filter-wise impact analysis on face recognition, age estimation, gender, and ethnicity prediction. The proposed method affirms the efficacy of our dataset with an accuracy of 87.25% and an optimal accuracy for facial attribute analysis.

Modern cloud services are prone to failures due to their complex architecture, making diagnosis a critical process. Site Reliability Engineers (SREs) spend hours leveraging multiple sources of data, including the alerts, error logs, and domain expertise through past experiences to locate the root cause(s). These experiences are documented as natural language text in outage reports for previous outages. However, utilizing the raw yet rich semi-structured information in the reports systematically is time-consuming. Structured information, on the other hand, such as alerts that are often used during fault diagnosis, is voluminous and requires expert knowledge to discern. Several strategies have been proposed to use each source of data separately for root cause analysis. In this work, we build a diagnostic service called ESRO that recommends root causes and remediation for failures by utilizing structured as well as semi-structured sources of data systematically. ESRO constructs a causal graph using alerts and a knowledge graph using outage reports, and merges them in a novel way to form a unified graph during training. A retrieval-based mechanism is then used to search the unified graph and rank the likely root causes and remediation techniques based on the alerts fired during an outage at inference time. Not only the individual alerts, but their respective importance in predicting an outage group is taken into account during recommendation. We evaluated our model on several cloud service outages of a large SaaS enterprise over the course of ~2 years, and obtained an average improvement of 27% in rouge scores after comparing the likely root causes against the ground truth over state-of-the-art baselines. We further establish the effectiveness of ESRO through qualitative analysis on multiple real outage examples., Comment: Accepted to 38th IEEE/ACM International Conference on Automated Software Engineering (ASE 2023)

In fair division problems, the notion of price of fairness measures the loss in welfare due to a fairness constraint. Prior work on the price of fairness has focused primarily on envy-freeness up to one good (EF1) as the fairness constraint, and on the utilitarian and egalitarian welfare measures. Our work instead focuses on the price of equitability up to one good (EQ1) (which we term price of equity) and considers the broad class of generalized $p$-mean welfare measures (which includes utilitarian, egalitarian, and Nash welfare as special cases). We derive fine-grained bounds on the price of equity in terms of the number of agent types (i.e., the maximum number of agents with distinct valuations), which allows us to identify scenarios where the existing bounds in terms of the number of agents are overly pessimistic. Our work focuses on the setting with binary additive valuations, and obtains upper and lower bounds on the price of equity for $p$-mean welfare for all $p \leqslant 1$. For any fixed $p$, our bounds are tight up to constant factors. A useful insight of our work is to identify the structure of allocations that underlie the upper (respectively, the lower) bounds simultaneously for all $p$-mean welfare measures, thus providing a unified structural understanding of price of fairness in this setting. This structural understanding, in fact, extends to the more general class of binary submodular (or matroid rank) valuations. We also show that, unlike binary additive valuations, for binary submodular valuations the number of agent types does not provide bounds on the price of equity., Comment: A version of this work was accepted for presentation at 16th International Symposium on Algorithmic Game Theory (SAGT 2023)

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover $\otilde(m^3)$-time \footnote{$\otilde$ hides factors that are logarithmic in the input size.}, constant-space algorithms for cycles of length at most $11$ and $\otilde(m^2)$-time, polynomial-space algorithms for paths of length at most $10$.

Much like most of cognition research, music cognition is an interdisciplinary field, which attempts to apply methods of cognitive science (neurological, computational and experimental) to understand the perception and process of composition of music. In this paper, we first motivate why music is relevant to cognitive scientists and give an overview of the approaches to computational modelling of music cognition. We then review literature on the various models of music perception, including non-computational models, computational non-cognitive models and computational cognitive models. Lastly, we review literature on modelling the creative behaviour and on computer systems capable of composing music. Since a lot of technical terms from music theory have been used, we have appended a list of relevant terms and their definitions at the end., Comment: TLDR: literature review of models of music cognition and composition

We report a demonstration of a high-entropy optical quantum random number generator (QRNG) based on photon arrival time. We have implemented the scheme with high-speed and high-precision electronics with a time resolution of 1 ps generating 115 Mbps raw data. The random bit generation efficiency is 8 bits per detection. The experimental data is quite consistent with theoretical estimation showing minimum bias. We apply a real-time information-theoretic randomness extractor to generate a final data rate of 109 Mbps. The randomness is rigorously evaluated against well-known statistical test suites of NIST, ENT, Diehard, TU-01 and Dieharder., Comment: 10 pages

Quantum key distribution (QKD) is an ingenious technology utilizing quantum information science for provable secure communication. However, owing to the technological limitations and device non-idealities it is important to analyze the system performance critically and carefully define the implementation security. With an acceleration in the commercial adoption of QKD, a simulation toolkit is requisite to evaluate the functional architecture of QKD protocols. We present a simulation framework to model optical and electrical components for implementing a QKD protocol. The present toolkit aims to model and simulate the optical path of the DPS-QKD protocol with its imperfections and eventually characterize the optical path. The detailed device-level modeling and analysis capabilities of the present toolkit based on Simulink and MATLAB have the potential to provide universal toolkit for practical design and implementation of generalized QKD protocols compared to earlier works. We report a novel work on the implementation of a QKD protocol on Simulink and MATLAB platform. Further, the absence of any modeling framework for DPS QKD and its simplistic optical schematic made it an obvious choice for the authors. We are hopeful that this work will pave way for simulating other QKD protocols from the DPR family., Comment: 10 pages