OpenRaiser/Intern-Atlas huggingface dataset:
Signal filtering to obtain number of Hamiltonian paths
Venue: arXiv cs.OH 2021
Year: 2021

This paper consists of two parts. First, the (undirected) Hamiltonian path problem is reduced to a signal filtering problem - number of Hamiltonian paths becomes amplitude at zero frequency for (a combination of) sinusoidal signal f(t) that encodes a graph. Then a 'divide and conquer' strategy to filtering out wide bandwidth components of a signal is suggested - one filters out angular frequency 1/2 to 1, then 1/4 to 1/2, then 1/8 to 1/4 and so on. An actual implementation of this strategy involves careful local polynomial extrapolation using numerical differentiation filters. When conjectures regarding required number of samples for specified filter designs and time complexity of obtaining filter coefficients hold, P=NP conditionally.
An aperiodic set of 11 Wang tiles
Venue: arXiv cs.DM 2021
Year: 2021

We present a new aperiodic tileset containing 11 Wang tiles on 4 colors, and we show that this tileset is minimal, in the sense that no Wang set with either fewer than 11 tiles or fewer than 4 colors is aperiodic. This gives a definitive answer to the problem raised by Wang in 1961.
Multi-Attribute Proportional Representation
Venue: arXiv cs.AI 2021
Year: 2021

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. Examples of applications include choosing members of a representative committee, where candidates are described by attributes such as sex, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computation complexity.
Market Segmentation in Online Platforms
Venue: arXiv cs.SI 2021
Year: 2021

This paper studies ranking policies in a stylized trial-offer marketplace model, in which a single firm offers products and has consumers with heterogeneous preferences. Consumer trials are influenced by past purchases and the ranking of each product. The platform owner needs to devise a ranking policy to display the products to maximize the number of purchases in the long run. The model proposed attempts to understand the impact of market segmentation in a trial-offer market with social influence. In our model, consumer choices are based on a very general choice model known as the mixed MNL. We analyze the long-term dynamics of this highly complex stochastic model and we quantify the expected benefits of market segmentation. When past purchases are displayed, consumer heterogeneity makes buyers try the sub-optimal products, reducing the overall sales rate. We show that consumer heterogeneity makes the ranking problem NP-hard. We then analyze the benefits of market segmentation. We find tight bounds to the expected benefits of offering a distinct ranking to each consumer segment. Finally, we show that the market segmentation strategy always benefits from social influence when the average quality ranking is used. One of the managerial implications is that the firm is better off using an aggregate ranking policy when the variety of consumer preference is limited, but it should perform a market segmentation policy when consumers are highly heterogeneous. We also show that this result is robust to relatively small consumer classification mistakes; when these are large, an aggregate ranking is preferred.
Introduzione all'Intelligenza Artificiale
Venue: arXiv cs.AI 2021
Year: 2021

The paper presents an introduction to Artificial Intelligence (AI) in an accessible and informal but precise form. The paper focuses on the algorithmic aspects of the discipline, presenting the main techniques used in AI systems groped in symbolic and subsymbolic. The last part of the paper is devoted to the discussion ongoing among experts in the field and the public at large about on the advantages and disadvantages of AI and in particular on the possible dangers. The personal opinion of the author on this subject concludes the paper. -- -- L'articolo presenta un'introduzione all'Intelligenza Artificiale (IA) in forma divulgativa e informale ma precisa. L'articolo affronta prevalentemente gli aspetti informatici della disciplina, presentando le principali tecniche usate nei sistemi di IA divise in simboliche e subsimboliche. L'ultima parte dell'articolo presenta il dibattito in corso tra gli esperi e il pubblico su vantaggi e svantaggi dell'IA e in particolare sui possibili pericoli. L'articolo termina con l'opinione dell'autore al riguardo.
An NFC-Enabled Anti-Counterfeiting System for Wine Industry
Venue: arXiv cs.CY 2021
Year: 2021

Wine counterfeiting has been posing significant challenges to wine industry, and has undermined the international wine trading market and the global economy hugely. The situation of counterfeiting has even been exacerbating in wine industry and global supply chain. There has been a number of anti-counterfeiting approaches which have been proposed and adopted utilizing different authentication technologies, in response to growing threats of counterfeiting to wine industry. The proposed NFC-Enabled Anti-Counterfeiting System (NAS) is developed for luxury-good industry such as wine industry, aiming at upholding provenance and authenticity of wine products from counterfeits via the product pedigree, transaction records and supply chain integrity maintained along the supply chain. Consumers can therefore safeguard their stake by authenticating a specific wine product with their NFC-enabled smartphones before purchasing at the retail points. NAS utilizes Near-field Communication (NFC), which has emerged as a promising technology and communication protocol for developing innovative alternatives, to facilitate the wine record processing of wine products and in turn combat wine and spirit counterfeiting. The integrated NAS is consisted of a wide range of hardware and software components, and the best combination of settings, parameters and deployments will therefore be identified. Other possible implementation issues, such as tag selection, tag programming and encryption, setup of back-end database servers and the design of NFC mobile application will also be discussed in this project. The critical design of NAS is vital not only to the key of product anti-counterfeiting of wine industry, but also to the strong foundation for other innovative supply chain solutions, such as the NFC-enabled purchasing system, developed on top of NAS with improved and integrated anti-counterfeiting functionalities.
Distributed Information-Theoretic Clustering
Venue: arXiv cs.IT 2021
Year: 2021

We study a novel multi-terminal source coding setup motivated by the biclustering problem. Two separate encoders observe two i.i.d. sequences $X^n$ and $Y^n$, respectively. The goal is to find rate-limited encodings $f(x^n)$ and $g(z^n)$ that maximize the mutual information $I(f(X^n); g(Y^n))/n$. We discuss connections of this problem with hypothesis testing against independence, pattern recognition, and the information bottleneck method. Improving previous cardinality bounds for the inner and outer bounds allows us to thoroughly study the special case of a binary symmetric source and to quantify the gap between the inner and the outer bound in this special case. Furthermore, we investigate a multiple description (MD) extension of the Chief Operating Officer (CEO) problem with mutual information constraint. Surprisingly, this MD-CEO problem permits a tight single-letter characterization of the achievable region.
Ragas in Bollywood music A microscopic view through multrifractal cross-correlation method
Venue: arXiv cs.SD 2021
Year: 2021

Since the start of Indian cinema, a number of films have been made where a particular song is based on a certain raga. These songs have been taking a major role in spreading the essence of classical music to the common people, who have no formal exposure to classical music. In this paper, we look to explore what are the particular features of a certain raga which make it understandable to common people and enrich the song to a great extent. For this, we chose two common ragas of Hindustani classical music, namely "Bhairav" and "Mian ki Malhar" which are known to have widespread application in popular film music. We have taken 3 minute clips of these two ragas from the renderings of two eminent maestros of Hindustani classical music. 3 min clips of ten (10) widely popular songs of Bollywood films were selected for analysis. These were analyzed with the help of a latest non linear analysis technique called Multifractal Detrended Cross correlation Analysis (MFDXA). With this technique, all parts of the Film music and the renderings from the eminent maestros are analyzed to find out a cross correlation coefficient (γx) which gives the degree of correlation between these two signals. We hypothesize that the parts which have the highest degree of cross correlation are the parts in which that particular raga is established in the song. Also the variation of cross correlation coefficient in the different parts of the two samples gives a measure of the modulation that is executed by the singer. Thus, in nutshell we try to study scientifically the amount of correlation that exists between the raga and the same raga being utilized in Film music. This will help in generating an automated algorithm through which a naïve listener will relish the flavor of a particular raga in a popular film song. The results are discussed in detail.
Variation of singing styles within a particular Gharana of Hindustani classical music A nonlinear multifractal study
Venue: arXiv cs.SD 2021
Year: 2021

Hindustani classical music is entirely based on the "Raga" structures. In Hindustani music, a "Gharana" or school refers to the adherence of a group of musicians to a particular musical style. Gharanas have their basis in the traditional mode of musical training and education. Every Gharana has its own distinct features; though within a particular Gharana, significant differences in singing styles are observed between generations of performers, which can be ascribed to the individual creativity of that singer. This work aims to study the evolution of singing style among four artists of four consecutive generations from Patiala Gharana. For this, alap and bandish parts of two different Ragas sung by the four artists were analyzed with the help of non linear multifractal analysis (MFDFA) technique. The multifractal spectral width obtained from the MFDFA method gives an estimate of the complexity of the signal. The observations from the variation of spectral width give a cue towards the scientific recognition of Guru-Shisya Parampara (teacher-student tradition) - a hitherto much-heard philosophical term. From a quantitative approach this study succeeds in analyzing the evolution of singing styles within a particular Gharana over generations of artists as well as the effect of globalization in the field of classical music.
Differentially Private Random Decision Forests using Smooth Sensitivity
Venue: arXiv cs.CR 2021
Year: 2021

We propose a new differentially-private decision forest algorithm that minimizes both the number of queries required, and the sensitivity of those queries. To do so, we build an ensemble of random decision trees that avoids querying the private data except to find the majority class label in the leaf nodes. Rather than using a count query to return the class counts like the current state-of-the-art, we use the Exponential Mechanism to only output the class label itself. This drastically reduces the sensitivity of the query -- often by several orders of magnitude -- which in turn reduces the amount of noise that must be added to preserve privacy. Our improved sensitivity is achieved by using "smooth sensitivity", which takes into account the specific data used in the query rather than assuming the worst-case scenario. We also extend work done on the optimal depth of random decision trees to handle continuous features, not just discrete features. This, along with several other improvements, allows us to create a differentially private decision forest with substantially higher predictive power than the current state-of-the-art.
Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections
Venue: arXiv cs.GT 2021
Year: 2021

The winner determination problems of many attractive multi-winner voting rules are NP-complete. However, they often admit polynomial-time algorithms when restricting inputs to be single-peaked. Commonly, such algorithms employ dynamic programming along the underlying axis. We introduce a new technique: carefully chosen integer linear programming (IP) formulations for certain voting problems admit an LP relaxation which is totally unimodular if preferences are single-peaked, and which thus admits an integral optimal solution. This technique gives efficient algorithms for finding optimal committees under Proportional Approval Voting (PAV) and the Chamberlin--Courant rule with single-peaked preferences, as well as for certain OWA-based rules. For PAV, this is the first technique able to efficiently find an optimal committee when preferences are single-peaked. An advantage of our approach is that no special-purpose algorithm needs to be used to exploit structure in the input preferences: any standard IP solver will terminate in the first iteration if the input is single-peaked, and will continue to work otherwise.
Warped Convolutions: Efficient Invariance to Spatial Transformations
Venue: arXiv cs.CV 2021
Year: 2021

Convolutional Neural Networks (CNNs) are extremely efficient, since they exploit the inherent translation-invariance of natural images. However, translation is just one of a myriad of useful spatial transformations. Can the same efficiency be attained when considering other spatial invariances? Such generalized convolutions have been considered in the past, but at a high computational cost. We present a construction that is simple and exact, yet has the same computational complexity that standard convolutions enjoy. It consists of a constant image warp followed by a simple convolution, which are standard blocks in deep learning toolboxes. With a carefully crafted warp, the resulting architecture can be made equivariant to a wide range of two-parameter spatial transformations. We show encouraging results in realistic scenarios, including the estimation of vehicle poses in the Google Earth dataset (rotation and scale), and face poses in Annotated Facial Landmarks in the Wild (3D rotations under perspective).
Online Algorithm for Demand Response with Inelastic Demands and Apparent Power Constraint
Venue: arXiv cs.DS 2021
Year: 2021

A classical problem in power systems is to allocate in-coming (elastic or inelastic) demands without violating the operating constraints of electric networks in an online fashion. Although online decision problems have been well-studied in the literature, a unique challenge arising in power systems is the presence of non-linear constraints, a departure from the traditional settings. A particular example is the capacity constraint of apparent power, which gives rise to a quadratic constraint, rather than typical linear constraints. In this paper, we present a competitive randomized online algorithm for deciding whether a sequence of inelastic demands can be allocated for the requested intervals, subject to the total satisfiable apparent power within a time-varying capacity constraint. We also consider an alternative setting with nodal voltage constraint, using a variant of the online algorithm. Finally, simulation studies are provided to evaluate the algorithms empirically.
A Characterisation of Open Bisimilarity using an Intuitionistic Modal Logic
Venue: arXiv cs.LO 2021
Year: 2021

Open bisimilarity is defined for open process terms in which free variables may appear. The insight is, in order to characterise open bisimilarity, we move to the setting of intuitionistic modal logics. The intuitionistic modal logic introduced, called $\mathcal{OM}$, is such that modalities are closed under substitutions, which induces a property known as intuitionistic hereditary. Intuitionistic hereditary reflects in logic the lazy instantiation of free variables performed when checking open bisimilarity. The soundness proof for open bisimilarity with respect to our intuitionistic modal logic is mechanised in Abella. The constructive content of the completeness proof provides an algorithm for generating distinguishing formulae, which we have implemented. We draw attention to the fact that there is a spectrum of bisimilarity congruences that can be characterised by intuitionistic modal logics.
Dirty Pixels: Towards End-to-End Image Processing and Perception
Venue: arXiv cs.CV 2021
Year: 2021

Real-world imaging systems acquire measurements that are degraded by noise, optical aberrations, and other imperfections that make image processing for human viewing and higher-level perception tasks challenging. Conventional cameras address this problem by compartmentalizing imaging from high-level task processing. As such, conventional imaging involves processing the RAW sensor measurements in a sequential pipeline of steps, such as demosaicking, denoising, deblurring, tone-mapping and compression. This pipeline is optimized to obtain a visually pleasing image. High-level processing, on the other hand, involves steps such as feature extraction, classification, tracking, and fusion. While this siloed design approach allows for efficient development, it also dictates compartmentalized performance metrics, without knowledge of the higher-level task of the camera system. For example, today's demosaicking and denoising algorithms are designed using perceptual image quality metrics but not with domain-specific tasks such as object detection in mind. We propose an end-to-end differentiable architecture that jointly performs demosaicking, denoising, deblurring, tone-mapping, and classification. The architecture learns processing pipelines whose outputs differ from those of existing ISPs optimized for perceptual quality, preserving fine detail at the cost of increased noise and artifacts. We demonstrate on captured and simulated data that our model substantially improves perception in low light and other challenging conditions, which is imperative for real-world applications. Finally, we found that the proposed model also achieves state-of-the-art accuracy when optimized for image reconstruction in low-light conditions, validating the architecture itself as a potentially useful drop-in network for reconstruction and analysis tasks beyond the applications demonstrated in this work.
Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
Venue: arXiv cs.LO 2021
Year: 2021

We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the $Σ_1$ theory is undecidable (already over two letters). We investigate the decidability border by considering fragments where all but a certain number of variables are alternation bounded, meaning that the variable must always be quantified over languages with a bounded number of letter alternations. We prove that when at most two variables are not alternation bounded, the $Σ_1$ fragment is decidable, and that it becomes undecidable when three variables are not alternation bounded. Regarding higher quantifier alternation depths, we prove that the $Σ_2$ fragment is undecidable already for one variable without alternation bound and that when all variables are alternation bounded, the entire first-order theory is decidable.
OptNet: Differentiable Optimization as a Layer in Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

This paper presents OptNet, a network architecture that integrates optimization problems (here, specifically in the form of quadratic programs) as individual layers in larger end-to-end trainable deep networks. These layers encode constraints and complex dependencies between the hidden states that traditional convolutional and fully-connected layers often cannot capture. We explore the foundations for such an architecture: we show how techniques from sensitivity analysis, bilevel optimization, and implicit differentiation can be used to exactly differentiate through these layers and with respect to layer parameters; we develop a highly efficient solver for these layers that exploits fast GPU-based batch solves within a primal-dual interior point method, and which provides backpropagation gradients with virtually no additional cost on top of the solve; and we highlight the application of these approaches in several problems. In one notable example, the method is learns to play mini-Sudoku (4x4) given just input and output games, with no a-priori information about the rules of the game; this highlights the ability of OptNet to learn hard constraints better than other neural architectures.
Use of the journal impact factor for assessing individual articles: Statistically flawed or not?
Venue: arXiv cs.DL 2021
Year: 2021

Most scientometricians reject the use of the journal impact factor for assessing individual articles and their authors. The well-known San Francisco Declaration on Research Assessment also strongly objects against this way of using the impact factor. Arguments against the use of the impact factor at the level of individual articles are often based on statistical considerations. The skewness of journal citation distributions typically plays a central role in these arguments. We present a theoretical analysis of statistical arguments against the use of the impact factor at the level of individual articles. Our analysis shows that these arguments do not support the conclusion that the impact factor should not be used for assessing individual articles. Using computer simulations, we demonstrate that under certain conditions the number of citations an article has received is a more accurate indicator of the value of the article than the impact factor. However, under other conditions, the impact factor is a more accurate indicator. It is important to critically discuss the dominant role of the impact factor in research evaluations, but the discussion should not be based on misplaced statistical arguments. Instead, the primary focus should be on the socio-technical implications of the use of the impact factor.
Causal Consistency for Reversible Multiparty Protocols
Venue: arXiv cs.LO 2021
Year: 2021

In programming models with a reversible semantics, computational steps can be undone. This paper addresses the integration of reversible semantics into process languages for communication-centric systems equipped with behavioral types. In prior work, we introduced a monitors-as-memories approach to seamlessly integrate reversible semantics into a process model in which concurrency is governed by session types (a class of behavioral types), covering binary (two-party) protocols with synchronous communication. The applicability and expressiveness of the binary setting, however, is limited. Here we extend our approach, and use it to define reversible semantics for an expressive process model that accounts for multiparty (n-party) protocols, asynchronous communication, decoupled rollbacks, and abstraction passing. As main result, we prove that our reversible semantics for multiparty protocols is causally-consistent. A key technical ingredient in our developments is an alternative reversible semantics with atomic rollbacks, which is conceptually simple and is shown to characterize decoupled rollbacks.