OpenRaiser/Intern-Atlas huggingface dataset:
Communication with Imperfectly Shared Randomness
Venue: arXiv cs.CC 2024
Year: 2024

The communication complexity of many fundamental problems reduces greatly when the communicating parties share randomness that is independent of the inputs to the communication task. Natural communication processes (say between humans) however often involve large amounts of shared correlations among the communicating players, but rarely allow for perfect sharing of randomness. Can the communication complexity benefit from shared correlations as well as it does from shared randomness? This question was considered mainly in the context of simultaneous communication by Bavarian et al. (ICALP 2014). In this work we study this problem in the standard interactive setting and give some general results. In particular, we show that every problem with communication complexity of $k$ bits with perfectly shared randomness has a protocol using imperfectly shared randomness with complexity $\exp(k)$ bits. We also show that this is best possible by exhibiting a promise problem with complexity $k$ bits with perfectly shared randomness which requires $\exp(k)$ bits when the randomness is imperfectly shared. Along the way we also highlight some other basic problems such as compression, and agreement distillation, where shared randomness plays a central role and analyze the complexity of these problems in the imperfectly shared randomness model. The technical highlight of this work is the lower bound that goes into the result showing the tightness of our general connection. This result builds on the intuition that communication with imperfectly shared randomness needs to be less sensitive to its random inputs than communication with perfectly shared randomness. The formal proof invokes results about the small-set expansion of the noisy hypercube and an invariance principle to convert this intuition to a proof, thus giving a new application domain for these fundamental results.
Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix are incoherent, we derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix. Although multiple works have been devoted to analyzing the recovery error of full-rank matrix completion, their error bounds are usually additive, making it impossible to obtain the perfect recovery case and more generally difficult to leverage the skewed distribution of eigenvalues. Our analysis is built upon the optimality condition of the regularized formulation and existing guarantees for low-rank matrix completion. To the best of our knowledge, this is the first relative bound that has been proved for the regularized formulation of matrix completion.
On Minimum Maximal Distance-k Matchings
Venue: arXiv cs.DM 2024
Year: 2024

We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $\ell \ge 1$ the problem of finding a minimum weight maximal distance-$2\ell$ matching and the problem of finding a minimum weight $(2 \ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $δ\ln |V(G)|$ unless $\mathrm{P} = \mathrm{NP}$, where $δ$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs. Note: This version (as compared to the journal submission) contains corrections to Section 4.
Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
Venue: arXiv cs.DS 2024
Year: 2024

We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both problems. This is close to the Ω(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.
Feature Selection Library (MATLAB Toolbox)
Venue: arXiv cs.CV 2024
Year: 2024

The Feature Selection Library (FSLib) introduces a comprehensive suite of feature selection (FS) algorithms for MATLAB, aimed at improving machine learning and data mining tasks. FSLib encompasses filter, embedded, and wrapper methods to cater to diverse FS requirements. Filter methods focus on the inherent characteristics of features, embedded methods incorporate FS within model training, and wrapper methods assess features through model performance metrics. By enabling effective feature selection, FSLib addresses the curse of dimensionality, reduces computational load, and enhances model generalizability. The elimination of redundant features through FSLib streamlines the training process, improving efficiency and scalability. This facilitates faster model development and boosts key performance indicators such as accuracy, precision, and recall by focusing on vital features. Moreover, FSLib contributes to data interpretability by revealing important features, aiding in pattern recognition and understanding. Overall, FSLib provides a versatile framework that not only simplifies feature selection but also significantly benefits the machine learning and data mining ecosystem by offering a wide range of algorithms, reducing dimensionality, accelerating model training, improving model outcomes, and enhancing data insights.
Low-complexity Image and Video Coding Based on an Approximate Discrete Tchebichef Transform
Venue: arXiv cs.MM 2024
Year: 2024

The usage of linear transformations has great relevance for data decorrelation applications, like image and video compression. In that sense, the discrete Tchebichef transform (DTT) possesses useful coding and decorrelation properties. The DTT transform kernel does not depend on the input data and fast algorithms can be developed to real time applications. However, the DTT fast algorithm presented in literature possess high computational complexity. In this work, we introduce a new low-complexity approximation for the DTT. The fast algorithm of the proposed transform is multiplication-free and requires a reduced number of additions and bit-shifting operations. Image and video compression simulations in popular standards shows good performance of the proposed transform. Regarding hardware resource consumption for FPGA shows 43.1% reduction of configurable logic blocks and ASIC place and route realization shows 57.7% reduction in the area-time figure when compared with the 2-D version of the exact DTT.
Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles
Venue: arXiv cs.AI 2024
Year: 2024

We study contextual linear bandit problems under feature uncertainty, where the features are noisy and have missing entries. To address the challenges posed by this noise, we analyze Bayesian oracles given the observed noisy features. Our Bayesian analysis reveals that the optimal hypothesis can significantly deviate from the underlying realizability function, depending on the noise characteristics. These deviations are highly non-intuitive and do not occur in classical noiseless setups. This implies that classical approaches cannot guarantee a non-trivial regret bound. Therefore, we propose an algorithm that aims to approximate the Bayesian oracle based on the observed information under this model, achieving $\tilde{O}(d\sqrt{T})$ regret bound when there is a large number of arms. We demonstrate the proposed algorithm using synthetic and real-world datasets.
Counterfactual Multi-Agent Policy Gradients
Venue: arXiv cs.AI 2024
Year: 2024

Cooperative multi-agent systems can be naturally used to model many real world problems, such as network packet routing and the coordination of autonomous vehicles. There is a great need for new reinforcement learning methods that can efficiently learn decentralised policies for such systems. To this end, we propose a new multi-agent actor-critic method called counterfactual multi-agent (COMA) policy gradients. COMA uses a centralised critic to estimate the Q-function and decentralised actors to optimise the agents' policies. In addition, to address the challenges of multi-agent credit assignment, it uses a counterfactual baseline that marginalises out a single agent's action, while keeping the other agents' actions fixed. COMA also uses a critic representation that allows the counterfactual baseline to be computed efficiently in a single forward pass. We evaluate COMA in the testbed of StarCraft unit micromanagement, using a decentralised variant with significant partial observability. COMA significantly improves average performance over other multi-agent actor-critic methods in this setting, and the best performing agents are competitive with state-of-the-art centralised controllers that get access to the full state.
Dependent randomized rounding for clustering and partition systems with knapsack constraints
Venue: arXiv cs.DS 2024
Year: 2024

Clustering problems are fundamental to unsupervised learning. There is an increased emphasis on fairness in machine learning and AI; one representative notion of fairness is that no single demographic group should be over-represented among the cluster-centers. This, and much more general clustering problems, can be formulated with "knapsack" and "partition" constraints. We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. Such bounds can be useful in inferring properties of large networks using few samples.
A logic for temporal conditionals and a solution to the Sea Battle Puzzle
Venue: arXiv cs.LO 2024
Year: 2024

Temporal reasoning with conditionals is more complex than both classical temporal reasoning and reasoning with timeless conditionals, and can lead to some rather counter-intuitive conclusions. For instance, Aristotle's famous "Sea Battle Tomorrow" puzzle leads to a fatalistic conclusion: whether there will be a sea battle tomorrow or not, but that is necessarily the case now. We propose a branching-time logic LTC to formalise reasoning about temporal conditionals and provide that logic with adequate formal semantics. The logic LTC extends the Nexttime fragment of CTL*, with operators for model updates, restricting the domain to only future moments where antecedent is still possible to satisfy. We provide formal semantics for these operators that implements the restrictor interpretation of antecedents of temporalized conditionals, by suitably restricting the domain of discourse. As a motivating example, we demonstrate that a naturally formalised in our logic version of the `Sea Battle' argument renders it unsound, thereby providing a solution to the problem with fatalist conclusion that it entails, because its underlying reasoning per cases argument no longer applies when these cases are treated not as material implications but as temporal conditionals. On the technical side, we analyze the semantics of LTC and provide a series of reductions of LTC-formulae, first recursively eliminating the dynamic update operators and then the path quantifiers in such formulae. Using these reductions we obtain a sound and complete axiomatization for LTC, and reduce its decision problem to that of the modal logic KD.
Sparse juntas on the biased hypercube
Venue: arXiv cs.CC 2024
Year: 2024

We give a structure theorem for Boolean functions on the $p$-biased hypercube which are $ε$-close to degree $d$ in $L_2$, showing that they are close to sparse juntas. Our structure theorem implies that such functions are $O(ε^{C_d} + p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$. We also give an analogous result for monotone Boolean functions on the biased hypercube which are $ε$-close to degree $d$ in $L_2$, showing that they are close to sparse DNFs. Our structure theorems are optimal in the following sense: for every $d,ε,p$, we identify a class $\mathcal{F}_{d,ε,p}$ of degree $d$ sparse juntas which are $O(ε)$-close to Boolean (in the monotone case, width $d$ sparse DNFs) such that a Boolean function on the $p$-biased hypercube is $O(ε)$-close to degree $d$ in $L_2$ iff it is $O(ε)$-close to a function in $\mathcal{F}_{d,ε,p}$.
FSSD: Feature Fusion Single Shot Multibox Detector
Venue: arXiv cs.CV 2024
Year: 2024

SSD (Single Shot Multibox Detector) is one of the best object detection algorithms with both high accuracy and fast speed. However, SSD's feature pyramid detection method makes it hard to fuse the features from different scales. In this paper, we proposed FSSD (Feature Fusion Single Shot Multibox Detector), an enhanced SSD with a novel and lightweight feature fusion module which can improve the performance significantly over SSD with just a little speed drop. In the feature fusion module, features from different layers with different scales are concatenated together, followed by some down-sampling blocks to generate new feature pyramid, which will be fed to multibox detectors to predict the final detection results. On the Pascal VOC 2007 test, our network can achieve 82.7 mAP (mean average precision) at the speed of 65.8 FPS (frame per second) with the input size 300$\times$300 using a single Nvidia 1080Ti GPU. In addition, our result on COCO is also better than the conventional SSD with a large margin. Our FSSD outperforms a lot of state-of-the-art object detection algorithms in both aspects of accuracy and speed. Code is available at https://github.com/lzx1413/CAFFE_SSD/tree/fssd.
Counting of Shortest Paths in Cubic Grid
Venue: arXiv cs.DM 2024
Year: 2024

The enumeration of shortest paths in cubic grid is presented herein, which could have importance in image processing and also in the network sciences. The cubic grid considers three neighborhoods - namely, 6-, 18- and 26-neighborhood related to face connectivity, edge connectivity and vertex connectivity, respectively. The formulation for distance metrics is given. L1, D18, and L_$\infty$ are the three metrics for 6-neighborhood, 18-neighborhood and 26-neighborhood. The task is to count the number of minimal paths, based on given neighborhood relations, from any given point to any other, in the three-dimensional cubic grid. Based on the coordinate triplets describing the grid, the formulations for the three neighborhoods are presented in this work. The problem both of theoretical importance and has several practical aspects.
Exploring Architectures for CNN-Based Word Spotting
Venue: arXiv cs.CV 2024
Year: 2024

The goal in word spotting is to retrieve parts of document images which are relevant with respect to a certain user-defined query. The recent past has seen attribute-based Convolutional Neural Networks take over this field of research. As is common for other fields of computer vision, the CNNs used for this task are already considerably deep. The question that arises, however, is: How complex does a CNN have to be for word spotting? Are increasingly deeper models giving increasingly better results or does performance behave asymptotically for these architectures? On the other hand, can similar results be obtained with a much smaller CNN? The goal of this paper is to give an answer to these questions. Therefore, the recently successful TPP-PHOCNet will be compared to a Residual Network, a Densely Connected Convolutional Network and a LeNet architecture empirically. As will be seen in the evaluation, a complex model can be beneficial for word spotting on harder tasks such as the IAM Offline Database but gives no advantage for easier benchmarks such as the George Washington Database.
Pack and Detect: Fast Object Detection in Videos Using Region-of-Interest Packing
Venue: arXiv cs.CV 2024
Year: 2024

Object detection in videos is an important task in computer vision for various applications such as object tracking, video summarization and video search. Although great progress has been made in improving the accuracy of object detection in recent years due to the rise of deep neural networks, the state-of-the-art algorithms are highly computationally intensive. In order to address this challenge, we make two important observations in the context of videos: (i) Objects often occupy only a small fraction of the area in each video frame, and (ii) There is a high likelihood of strong temporal correlation between consecutive frames. Based on these observations, we propose Pack and Detect (PaD), an approach to reduce the computational requirements of object detection in videos. In PaD, only selected video frames called anchor frames are processed at full size. In the frames that lie between anchor frames (inter-anchor frames), regions of interest (ROIs) are identified based on the detections in the previous frame. We propose an algorithm to pack the ROIs of each inter-anchor frame together into a reduced-size frame. The computational requirements of the detector are reduced due to the lower size of the input. In order to maintain the accuracy of object detection, the proposed algorithm expands the ROIs greedily to provide additional background around each object to the detector. PaD can use any underlying neural network architecture to process the full-size and reduced-size frames. Experiments using the ImageNet video object detection dataset indicate that PaD can potentially reduce the number of FLOPS required for a frame by $4\times$. This leads to an overall increase in throughput of $1.25\times$ on a 2.1 GHz Intel Xeon server with a NVIDIA Titan X GPU at the cost of $1.1\%$ drop in accuracy.
Probabilistic Analysis of Edge Elimination for Euclidean TSP
Venue: arXiv cs.DM 2024
Year: 2024

One way to speed up the calculation of optimal TSP tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so several edge elimination approaches have been proposed in the past. In this work we investigate two of them in the scenario where the input consists of $n$ independently distributed random points in the 2-dimensional unit square with bounded density function from above and below by arbitrary positive constants. We show that after the edge elimination procedure of Hougardy and Schroeder the expected number of remaining edges is $Θ(n)$, while after that the non-recursive part of Jonker and Volgenant the expected number of remaining edges is $Θ(n^2)$.
$m$-adic residue codes over $\mathbb{F}_q[v]/(v^s-v)$ and their application to quantum codes
Venue: arXiv cs.IT 2024
Year: 2024

Due to their rich algebraic structure, cyclic codes have a great deal of significance amongst linear codes. Duadic codes are the generalization of the quadratic residue codes, a special case of cyclic codes. The $m$-adic residue codes are the generalization of the duadic codes. The aim of this paper is to study the structure of the $m$-adic residue codes over the quotient ring $\frac{{{\mathbb{F}_q}\left[ v \right]}}{{\left\langle {{v^s} - v} \right\rangle }}$. We determine the idempotent generators of the $m$-adic residue codes over $\frac{{{\mathbb{F}_q}\left[ v \right]}}{{\left\langle {{v^s} - v} \right\rangle }}$. We obtain some parameters of optimal $m$-adic residue codes over $\frac{{{\mathbb{F}_q}\left[ v \right]}}{{\left\langle {{v^s} - v} \right\rangle }}$ with respect to Griesmer bound for rings. Furthermore, we derive a condition for $m$-adic residue codes over $\frac{{{\mathbb{F}_q}\left[ v \right]}}{{\left\langle {{v^s} - v} \right\rangle }}$ to contain their dual. By making use of a preserving-orthogonality Gray map, we construct a family of quantum error correcting codes from the Gray images of dual-containing $m$-adic residue codes over $\frac{{{\mathbb{F}_q}\left[ v \right]}}{{\left\langle {{v^s} - v} \right\rangle }}$ and give some examples to illustrate our findings.
On the Maximum Distance Sublattice Problem and Closest Vector Problem
Venue: arXiv cs.CC 2024
Year: 2024

In this paper, we introduce the Maximum Distance Sublattice Problem (MDSP). We observed that the problem of solving an instance of the Closest Vector Problem (CVP) in a lattice $\mathcal{L}$ is the same as solving an instance of MDSP in the dual lattice of $\mathcal{L}$. We give an alternate reduction between the CVP and MDSP. This alternate reduction does not use the concept of dual lattice.
State of the Art in Fair ML: From Moral Philosophy and Legislation to Fair Classifiers
Venue: arXiv cs.CY 2024
Year: 2024

Machine learning is becoming an ever present part in our lives as many decisions, e.g. to lend a credit, are no longer made by humans but by machine learning algorithms. However those decisions are often unfair and discriminating individuals belonging to protected groups based on race or gender. With the recent General Data Protection Regulation (GDPR) coming into effect, new awareness has been raised for such issues and with computer scientists having such a large impact on peoples lives it is necessary that actions are taken to discover and prevent discrimination. This work aims to give an introduction into discrimination, legislative foundations to counter it and strategies to detect and prevent machine learning algorithms from showing such behavior.
Differential Similarity in Higher Dimensional Spaces: Theory and Applications
Venue: arXiv cs.LG 2024
Year: 2024

This paper presents an extension and an elaboration of the theory of differential similarity, which was originally proposed in arXiv:1401.2411 [cs.LG]. The goal is to develop an algorithm for clustering and coding that combines a geometric model with a probabilistic model in a principled way. For simplicity, the geometric model in the earlier paper was restricted to the three-dimensional case. The present paper removes this restriction, and considers the full $n$-dimensional case. Although the mathematical model is the same, the strategies for computing solutions in the $n$-dimensional case are different, and one of the main purposes of this paper is to develop and analyze these strategies. Another main purpose is to devise techniques for estimating the parameters of the model from sample data, again in $n$ dimensions. We evaluate the solution strategies and the estimation techniques by applying them to two familiar real-world examples: the classical MNIST dataset and the CIFAR-10 dataset.