OpenRaiser/Intern-Atlas huggingface dataset:
What can be sampled locally?
Venue: arXiv cs.DS 2022
Year: 2022

The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved locally: for a given local CSP whether a CSP solution can be constructed by a distributed algorithm using local information. In this paper, we consider the problem of sampling a uniform CSP solution by distributed algorithms, and ask whether a locally definable joint distribution can be sampled from locally. More broadly, we consider sampling from Gibbs distributions induced by weighted local CSPs in the LOCAL model. We give two Markov chain based distributed algorithms which we believe to represent two fundamental approaches for sampling from Gibbs distributions via distributed algorithms. The first algorithm generically parallelizes the single-site sequential Markov chain by iteratively updating a random independent set of variables in parallel, and achieves an $O(Δ\log n)$ time upper bound in the LOCAL model, where $Δ$ is the maximum degree, when the Dobrushin's condition for the Gibbs distribution is satisfied. The second algorithm is a novel parallel Markov chain which proposes to update all variables simultaneously yet still guarantees to converge correctly with no bias. It surprisingly parallelizes an intrinsically sequential process: stabilizing to a joint distribution with massive local dependencies, and may achieve an optimal $O(\log n)$ time upper bound independent of the maximum degree $Δ$ under a stronger mixing condition. We also show a strong $Ω(diam)$ lower bound for sampling independent set in graphs with maximum degree $Δ\ge 6$. This lower bound holds even when every node is aware of the graph. This gives a strong separation between sampling and constructing locally checkable labelings.
A New Graph Parameter To Measure Linearity
Venue: arXiv cs.DS 2022
Year: 2022

Consider a sequence of LexBFS vertex orderings σ1, σ2, . . . where each ordering σi is used to break ties for σi+1. Since the total number of vertex orderings of a finite graph is finite, this sequence must end in a cycle of vertex orderings. The possible length of this cycle is the main subject of this work. Intuitively, we prove for graphs with a known notion of linearity (e.g., interval graphs with their interval representation on the real line), this cycle cannot be too big, no matter which vertex ordering we start with. More precisely, it was conjectured in [9] that for cocomparability graphs, the size of this cycle is always 2, independent of the starting order. Furthermore [27] asked whether for arbitrary graphs, the size of such a cycle is always bounded by the asteroidal number of the graph. In this work, while we answer this latter question negatively, we provide support for the conjecture on cocomparability graphs by proving it for the subclass of domino-free cocomparability graphs. This subclass contains cographs, proper interval, interval, and cobipartite graphs. We also provide simpler independent proofs for each of these cases which lead to stronger results on this subclasses.
New Results On Routing Via Matchings On Graphs
Venue: arXiv cs.DS 2022
Year: 2022

In this paper we present some new complexity results on the routing time of a graph under the \textit{routing via matching} model. This is a parallel routing model which was introduced by Alon et al\cite{alon1994routing}. The model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data (pebbles) with its matched partner. Let $G$ be a connected graph with vertices labeled from $\{1,...,n\}$ and the destination vertices of the pebbles are given by a permutation $π$. The problem is to find a minimum step routing scheme for the input permutation $π$. This is denoted as the routing time $rt(G,π)$ of $G$ given $π$. In this paper we characterize the complexity of some known problems under the routing via matching model and discuss their relationship to graph connectivity and clique number. We also introduce some new problems in this domain, which may be of independent interest.
A subexponential parameterized algorithm for Directed Subset Traveling Salesman Problem on planar graphs
Venue: arXiv cs.DS 2022
Year: 2022

There are numerous examples of the so-called ``square root phenomenon'' in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter $k$, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in $O(\sqrt{k})$ instead of $O(k)$ (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals $T$ by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number $k=|T|$ of terminals is regarded as the parameter. We show that Subset TSP can be solved in time $2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}$ even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.
Theoretical insights into the optimization landscape of over-parameterized shallow neural networks
Venue: arXiv cs.LG 2022
Year: 2022

In this paper we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the number of observations are fewer than the number of parameters in the model. We show that with quadratic activations the optimization landscape of training such shallow neural networks has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.
Double-Opportunity Estimation via Altruism
Venue: arXiv cs.SY 2022
Year: 2022

A novel approach, based on the notion of altruism, is presented to cooperative parameter estimation in a system comprising two information-sharing agents. The underlying assumption is that the overall two-agent scheme can reach desired performance level even if only one of the agents performs satisfactorily, hence there exist two independent opportunities to estimate. The notion of altruism motivates a new definition of cooperative estimation optimality that generalizes the common definition of minimum mean squared error optimality. Fundamental equations are derived for two types of altruistic cooperative estimation problems, corresponding to heterarchical and hierarchical setups. Although these equations are, generally, hard to solve, their solution in the Gaussian case is straightforward and only entails the computation of the largest eigenvalue of the conditional covariance matrix and its corresponding eigenvector. Moreover, in the Gaussian case the performance improvement of the two altruistic cooperative estimation techniques over the conventional (egoistic) estimation approach is shown to depend on the problem's dimensionality and statistical distribution. In particular, the performance improvement grows with the dispersion of the spectrum of the conditional covariance matrix, rendering the new estimation approach especially appealing in ill-conditioned problems. The validity of the solution in the Gaussian case is illustrated numerically.
Contrast Enhancement of Brightness-Distorted Images by Improved Adaptive Gamma Correction
Venue: arXiv cs.MM 2022
Year: 2022

As an efficient image contrast enhancement (CE) tool, adaptive gamma correction (AGC) was previously proposed by relating gamma parameter with cumulative distribution function (CDF) of the pixel gray levels within an image. ACG deals well with most dimmed images, but fails for globally bright images and the dimmed images with local bright regions. Such two categories of brightness-distorted images are universal in real scenarios, such as improper exposure and white object regions. In order to attenuate such deficiencies, here we propose an improved AGC algorithm. The novel strategy of negative images is used to realize CE of the bright images, and the gamma correction modulated by truncated CDF is employed to enhance the dimmed ones. As such, local over-enhancement and structure distortion can be alleviated. Both qualitative and quantitative experimental results show that our proposed method yields consistently good CE results.
Creating a Linked Data-Friendly Metadata Application Profile for Archival Description
Venue: arXiv cs.DL 2022
Year: 2022

We provide an overview of efforts to apply and extend Schema.org for archives and archival description. The authors see the application of Schema.org and extensions as a low barrier means to publish easily consumable linked data about archival resources, institutions that hold them, and contextual entities such as people and organizations responsible for their creation.
How to be Helpful? Supportive Behaviors and Personalization for Human-Robot Collaboration
Venue: arXiv cs.RO 2022
Year: 2022

The field of Human-Robot Collaboration (HRC) has seen a considerable amount of progress in recent years. Thanks in part to advances in control and perception algorithms, robots have started to work in increasingly unstructured environments, where they operate side by side with humans to achieve shared tasks. However, little progress has been made toward the development of systems that are truly effective in supporting the human, proactive in their collaboration, and that can autonomously take care of part of the task. In this work, we present a collaborative system capable of assisting a human worker despite limited manipulation capabilities, incomplete model of the task, and partial observability of the environment. Our framework leverages information from a high-level, hierarchical model that is shared between the human and robot and that enables transparent synchronization between the peers and mutual understanding of each other's plan. More precisely, we firstly derive a partially observable Markov model from the high-level task representation; we then use an online Monte-Carlo solver to compute a short-horizon robot-executable plan. The resulting policy is capable of interactive replanning on-the-fly, dynamic error recovery, and identification of hidden user preferences. We demonstrate that the system is capable of robustly providing support to the human in a realistic furniture construction task.
How to Charge Lightning: The Economics of Bitcoin Transaction Channels
Venue: arXiv cs.CR 2022
Year: 2022

Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies. However, the economic effect of transaction channels on the system has not been explored much until now. We study the economics of Bitcoin transaction channels, and present a framework for an economic analysis of the lightning network and its effect on transaction fees on the blockchain. Our framework allows us to reason about different patterns of demand for transactions and different topologies of the lightning network, and to derive the resulting fees for transacting both on and off the blockchain. Our initial results indicate that while the lightning network does allow for a substantially higher number of transactions to pass through the system, it does not necessarily provide higher fees to miners, and as a result may in fact lead to lower participation in mining within the system.
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Venue: arXiv cs.DS 2022
Year: 2022

We present $O(\log\log n)$-round algorithms in the Massively Parallel Computation (MPC) model, with $\tilde{O}(n)$ memory per machine, that compute a maximal independent set, a $1+ε$ approximation of maximum matching, and a $2+ε$ approximation of minimum vertex cover, for any $n$-vertex graph and any constant $ε>0$. These improve the state of the art as follows: - Our MIS algorithm leads to a simple $O(\log\log Δ)$-round MIS algorithm in the Congested Clique model of distributed computing, which improves on the $\tilde{O}(\sqrt{\log Δ})$-round algorithm of Ghaffari [PODC'17]. - Our $O(\log\log n)$-round $(1+ε)$-approximate maximum matching algorithm simplifies or improves on the following prior work: $O(\log^2\log n)$-round $(1+ε)$-approximation algorithm of Czumaj et al. [STOC'18] and $O(\log\log n)$-round $(1+ε)$-approximation algorithm of Assadi et al. [SODA'19]. - Our $O(\log\log n)$-round $(2+ε)$-approximate minimum vertex cover algorithm improves on an $O(\log\log n)$-round $O(1)$-approximation of Assadi et al. [arXiv'17].
Data-Augmented Contact Model for Rigid Body Simulation
Venue: arXiv cs.RO 2022
Year: 2022

Accurately modeling contact behaviors for real-world, near-rigid materials remains a grand challenge for existing rigid-body physics simulators. This paper introduces a data-augmented contact model that incorporates analytical solutions with observed data to predict the 3D contact impulse which could result in rigid bodies bouncing, sliding or spinning in all directions. Our method enhances the expressiveness of the standard Coulomb contact model by learning the contact behaviors from the observed data, while preserving the fundamental contact constraints whenever possible. For example, a classifier is trained to approximate the transitions between static and dynamic frictions, while non-penetration constraint during collision is enforced analytically. Our method computes the aggregated effect of contact for the entire rigid body, instead of predicting the contact force for each contact point individually, maintaining same simulation speed as the number of contact points increases for detailed geometries. Supplemental video: https://shorturl.at/eilwX Keywords: Physics Simulation Algorithms, Dynamics Learning, Contact Learning
A $5k$-vertex Kernel for $P_2$-packing
Venue: arXiv cs.DS 2022
Year: 2022

The $P_2$-packing problem asks for whether a graph contains $k$ vertex-disjoint paths each of length two. We continue the study of its kernelization algorithms, and develop a $5k$-vertex kernel.
Multi-focus Noisy Image Fusion using Low-Rank Representation
Venue: arXiv cs.CV 2022
Year: 2022

Multi-focus noisy image fusion represents an important task in the field of image fusion which generates a single, clear and focused image from all source images. In this paper, we propose a novel multi-focus noisy image fusion method based on low-rank representation (LRR) which is a powerful tool in representation learning. A multi-scale transform framework is adopted in which source images are decomposed into low frequency and high frequency coefficients, respectively. For low frequency coefficients, the fused low frequency coefficients are determined by a spatial frequency strategy, while the high frequency coefficients are fused by the LRR-based fusion strategy. Finally, the fused image is reconstructed by inverse multi-scale transforms with fused coefficients. Experimental results demonstrate that the proposed algorithm offers state-of-the-art performance even when the source images contain noise. The Code of our fusion method is available at https://github.com/hli1221/imagefusion_noisy_lrr
Machine Learning: The Basics
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning (ML) has become a commodity in our every-day lives. We routinely ask ML empowered smartphones to suggest lovely food places or to guide us through a strange place. ML methods have also become standard tools in many fields of science and engineering. A plethora of ML applications transform human lives at unprecedented pace and scale. This book portrays ML as the combination of three basic components: data, model and loss. ML methods combine these three components within computationally efficient implementations of the basic scientific principle "trial and error". This principle consists of the continuous adaptation of a hypothesis about a phenomenon that generates data. ML methods use a hypothesis to compute predictions for future events. We believe that thinking about ML as combinations of three components given by data, model, and loss helps to navigate the steadily growing offer for ready-to-use ML methods. Our three-component picture of ML allows a unified treatment of a wide range of concepts and techniques which seem quite unrelated at first sight. The regularization effect of early stopping in iterative methods is due to the shrinking of the effective hypothesis space. Privacy-preserving ML is obtained by particular choices for the features of data points. Explainable ML methods are characterized by particular choices for the hypothesis space. To make good use of ML tools it is instrumental to understand its underlying principles at different levels of detail. On a lower level, this tutorial helps ML engineers to choose suitable methods for the application at hand. The book also offers a higher-level view on the implementation of ML methods which is typically required to manage a team of ML engineers and data scientists.
Revisiting the tree edit distance and its backtracing: A tutorial
Venue: arXiv cs.DS 2022
Year: 2022

Almost 30 years ago, Zhang and Shasha (1989) published a seminal paper describing an efficient dynamic programming algorithm computing the tree edit distance, that is, the minimum number of node deletions, insertions, and replacements that are necessary to transform one tree into another. Since then, the tree edit distance has been widely applied, for example in biology and intelligent tutoring systems. However, the original paper of Zhang and Shasha can be challenging to read for newcomers and it does not describe how to efficiently infer the optimal edit script. In this contribution, we provide a comprehensive tutorial to the tree edit distance algorithm of Zhang and Shasha. We further prove metric properties of the tree edit distance, and describe efficient algorithms to infer the cheapest edit script, as well as a summary of all cheapest edit scripts between two trees.
Zip Trees
Venue: arXiv cs.DS 2022
Year: 2022

We introduce the zip tree, a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps (Seidel and Aragon 1996), except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths ("unzipping" and "zipping") rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion (Stephenson 1980; Martínez and Roura 1998; Sprugnoli 1980). From a theoretical standpoint, this work provides two main results. First, zip trees require only $O(\log \log n)$ bits (with high probability) to represent the largest rank in an $n$-node binary search tree; previous data structures require $O(\log n)$ bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists (Pugh 1990), and simplify the mapping of (Dean and Jones 2007) between skip lists and binary search trees.
Notes on Abstract Argumentation Theory
Venue: arXiv cs.AI 2022
Year: 2022

This note reviews Section 2 of Dung's seminal 1995 paper on abstract argumentation theory. In particular, we clarify and make explicit all of the proofs mentioned therein, and provide more examples to illustrate the definitions, with the aim to help readers approaching abstract argumentation theory for the first time. However, we provide minimal commentary and will refer the reader to Dung's paper for the intuitions behind various concepts. The appropriate mathematical prerequisites are provided in the appendices.
Road surface 3d reconstruction based on dense subpixel disparity map estimation
Venue: arXiv cs.CV 2022
Year: 2022

Various 3D reconstruction methods have enabled civil engineers to detect damage on a road surface. To achieve the millimetre accuracy required for road condition assessment, a disparity map with subpixel resolution needs to be used. However, none of the existing stereo matching algorithms are specially suitable for the reconstruction of the road surface. Hence in this paper, we propose a novel dense subpixel disparity estimation algorithm with high computational efficiency and robustness. This is achieved by first transforming the perspective view of the target frame into the reference view, which not only increases the accuracy of the block matching for the road surface but also improves the processing speed. The disparities are then estimated iteratively using our previously published algorithm where the search range is propagated from three estimated neighbouring disparities. Since the search range is obtained from the previous iteration, errors may occur when the propagated search range is not sufficient. Therefore, a correlation maxima verification is performed to rectify this issue, and the subpixel resolution is achieved by conducting a parabola interpolation enhancement. Furthermore, a novel disparity global refinement approach developed from the Markov Random Fields and Fast Bilateral Stereo is introduced to further improve the accuracy of the estimated disparity map, where disparities are updated iteratively by minimising the energy function that is related to their interpolated correlation polynomials. The algorithm is implemented in C language with a near real-time performance. The experimental results illustrate that the absolute error of the reconstruction varies from 0.1 mm to 3 mm.
Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Venue: arXiv cs.LG 2022
Year: 2022

We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power $α=1/2$ and reduced-variance loss estimators. More generally, we define an adversarial regime with a self-bounding constraint, which includes stochastic regime, stochastically constrained adversarial regime (Wei and Luo), and stochastic regime with adversarial corruptions (Lykouris et al.) as special cases, and show that the algorithm achieves logarithmic regret guarantee in this regime and all of its special cases simultaneously with the adversarial regret guarantee.} The algorithm also achieves adversarial and stochastic optimality in the utility-based dueling bandit setting. We provide empirical evaluation of the algorithm demonstrating that it significantly outperforms UCB1 and EXP3 in stochastic environments. We also provide examples of adversarial environments, where UCB1 and Thompson Sampling exhibit almost linear regret, whereas our algorithm suffers only logarithmic regret. To the best of our knowledge, this is the first example demonstrating vulnerability of Thompson Sampling in adversarial environments. Last, but not least, we present a general stochastic analysis and a general adversarial analysis of OMD algorithms with Tsallis entropy regularization for $α\in[0,1]$ and explain the reason why $α=1/2$ works best.