OpenRaiser/Intern-Atlas huggingface dataset:
Error Tolerant Path Planning for Swarms of Micro Aerial Vehicles with Quality Amplification
Venue: arXiv cs.RO 2021
Year: 2021

We present an error tolerant path planning algorithm for Micro Aerial Vehicle (MAV) swarms. We assume navigation without GPS-like techniques. The MAVs find their path using sensors and cameras, identifying and following a series of visual landmarks. The visual landmarks lead the MAVs towards their destination. MAVs are assumed to be unaware of the terrain and locations of the landmarks. They hold a priori information about landmarks, whose interpretation is prone to errors. Errors are of two types, recognition or advice. Recognition errors follow from misinterpretation of sensed data or a priori information, or confusion of objects, e.g., due to faulty sensors. Advice errors are consequences of outdated or wrong information about landmarks, e.g., due to weather conditions. Our path planning algorithm is cooperative. MAVs communicate and exchange information wirelessly, to minimize the number of recognition and advice errors. Hence, the quality of the navigation decision process is amplified. Our solution successfully achieves an adaptive error tolerant navigation system. Quality amplification is parameterized with respect to the number of MAVs. We validate our approach with theoretical proofs and numeric simulations.
The Cost of a Reductions Approach to Private Fair Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Through the lens of information-theoretic reductions, we examine a reductions approach to fair optimization and learning where a black-box optimizer is used to learn a fair model for classification or regression. Quantifying the complexity, both statistically and computationally, of making such models satisfy the rigorous definition of differential privacy is our end goal. We resolve a few open questions and show applicability to fair machine learning, hypothesis testing, and to optimizing non-standard measures of classification loss. Furthermore, our sample complexity bounds are tight amongst all strategies that jointly minimize a composition of functions. The reductions approach to fair optimization can be abstracted as the constrained group-objective optimization problem where we aim to optimize an objective that is a function of losses of individual groups, subject to some constraints. We give the first polynomial-time algorithms to solve the problem with $(ε, 0)$ or $(ε, δ)$ differential privacy guarantees when defined on a convex decision set (for example, the $\ell_P$ unit ball) with convex constraints and losses. Accompanying information-theoretic lower bounds for the problem are presented. In addition, compared to a previous method for ensuring differential privacy subject to a relaxed form of the equalized odds fairness constraint, the $(ε, δ)$-differentially private algorithm we present provides asymptotically better sample complexity guarantees, resulting in an exponential improvement in certain parameter regimes. We introduce a class of bounded divergence linear optimizers, which could be of independent interest, and specialize to pure and approximate differential privacy.
When is the best time to learn? -- Evidence from an introductory statistics course
Venue: arXiv cs.CY 2021
Year: 2021

We analyze learning data of an e-assessment platform for an introductory mathematical statistics course, more specifically the time of the day when students learn. We propose statistical models to predict students' success and to describe their behavior with a special focus on the following aspects. First, we find that learning during daytime and not at nighttime is a relevant variable for predicting success in final exams. Second, we observe that good and very good students tend to learn in the afternoon, while some students who failed our course were more likely to study at night but not successfully so. Third, we discuss the average time spent on exercises. Regarding this, students who participated in an exam spent more time doing exercises than students who dropped the course before.
A Theoretical Connection Between Statistical Physics and Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Sequential decision making in the presence of uncertainty and stochastic dynamics gives rise to distributions over state/action trajectories in reinforcement learning (RL) and optimal control problems. This observation has led to a variety of connections between RL and inference in probabilistic graphical models (PGMs). Here we explore a different dimension to this relationship, examining reinforcement learning using the tools and abstractions of statistical physics. The central object in the statistical physics abstraction is the idea of a partition function $\mathcal{Z}$, and here we construct a partition function from the ensemble of possible trajectories that an agent might take in a Markov decision process. Although value functions and $Q$-functions can be derived from this partition function and interpreted via average energies, the $\mathcal{Z}$-function provides an object with its own Bellman equation that can form the basis of alternative dynamic programming approaches. Moreover, when the MDP dynamics are deterministic, the Bellman equation for $\mathcal{Z}$ is linear, allowing direct solutions that are unavailable for the nonlinear equations associated with traditional value functions. The policies learned via these $\mathcal{Z}$-based Bellman updates are tightly linked to Boltzmann-like policy parameterizations. In addition to sampling actions proportionally to the exponential of the expected cumulative reward as Boltzmann policies would, these policies take entropy into account favoring states from which many outcomes are possible.
Robustness Against Transactional Causal Consistency
Venue: arXiv cs.PL 2021
Year: 2021

Distributed storage systems and databases are widely used by various types of applications. Transactional access to these storage systems is an important abstraction allowing application programmers to consider blocks of actions (i.e., transactions) as executing atomically. For performance reasons, the consistency models implemented by modern databases are weaker than the standard serializability model, which corresponds to the atomicity abstraction of transactions executing over a sequentially consistent memory. Causal consistency for instance is one such model that is widely used in practice. In this paper, we investigate application-specific relationships between several variations of causal consistency and we address the issue of verifying automatically if a given transactional program is robust against causal consistency, i.e., all its behaviors when executed over an arbitrary causally consistent database are serializable. We show that programs without write-write races have the same set of behaviors under all these variations, and we show that checking robustness is polynomial time reducible to a state reachability problem in transactional programs over a sequentially consistent shared memory. A surprising corollary of the latter result is that causal consistency variations which admit incomparable sets of behaviors admit comparable sets of robust programs. This reduction also opens the door to leveraging existing methods and tools for the verification of concurrent programs (assuming sequential consistency) for reasoning about programs running over causally consistent databases. Furthermore, it allows to establish that the problem of checking robustness is decidable when the programs executed at different sites are finite-state.
Algorithms for weighted independent transversals and strong colouring
Venue: arXiv cs.DS 2021
Year: 2021

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph with a given vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best bounds given by nonconstructive results, and those obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this paper we develop a randomized version of this algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.
DIEL: Interactive Visualization Beyond the Here and Now
Venue: arXiv cs.DB 2021
Year: 2021

Interactive visualization design and research have primarily focused on local data and synchronous events. However, for more complex use cases---e.g., remote database access and streaming data sources---developers must grapple with distributed data and asynchronous events. Currently, constructing these use cases is difficult and time-consuming; developers are forced to operationally program low-level details like asynchronous database querying and reactive event handling. This approach is in stark contrast to modern methods for browser-based interactive visualization, which feature high-level declarative specifications. In response, we present DIEL, a declarative framework that supports asynchronous events over distributed data. Like many declarative visualization languages, DIEL developers need only specify what data they want, rather than procedural steps for how to assemble it; uniquely, DIEL models asynchronous events (e.g., user interactions or server responses) as streams of data that are captured in event logs. To specify the state of a user interface at any time, developers author declarative queries over the data and event logs; DIEL compiles and optimizes a corresponding dataflow graph, and synthesizes necessary low-level distributed systems details. We demonstrate DIEL's performance and expressivity through ex-ample interactive visualizations that make diverse use of remote data and coordination of asynchronous events. We further evaluate DIEL's usability using the Cognitive Dimensions of Notations framework, revealing wins such as ease of change, and compromises such as premature commitments.
Dynamic Face Video Segmentation via Reinforcement Learning
Venue: arXiv cs.CV 2021
Year: 2021

For real-time semantic video segmentation, most recent works utilised a dynamic framework with a key scheduler to make online key/non-key decisions. Some works used a fixed key scheduling policy, while others proposed adaptive key scheduling methods based on heuristic strategies, both of which may lead to suboptimal global performance. To overcome this limitation, we model the online key decision process in dynamic video segmentation as a deep reinforcement learning problem and learn an efficient and effective scheduling policy from expert information about decision history and from the process of maximising global return. Moreover, we study the application of dynamic video segmentation on face videos, a field that has not been investigated before. By evaluating on the 300VW dataset, we show that the performance of our reinforcement key scheduler outperforms that of various baselines in terms of both effective key selections and running speed. Further results on the Cityscapes dataset demonstrate that our proposed method can also generalise to other scenarios. To the best of our knowledge, this is the first work to use reinforcement learning for online key-frame decision in dynamic video segmentation, and also the first work on its application on face videos.
RadVR: A 6DOF Virtual Reality Daylighting Analysis Tool
Venue: arXiv cs.GR 2021
Year: 2021

This work introduces RadVR, a virtual reality tool for daylighting analysis that simultaneously combines qualitative assessments through immersive real-time renderings with quantitative physically correct daylighting simulations in a 6DOF virtual environment. By taking a 3D building model with material properties as input, RadVR allows users to (1) perform physically-based daylighting simulations via Radiance, (2) study sunlight in different hours-of-the-year, (3) interact with a 9-point-in-time matrix for the most representative times of the year, and (4) visualize, compare, and analyze daylighting simulation results. With an end-to-end workflow, RadVR integrates with 3D modeling software that is commonly used by building designers. Additionally, by conducting user experiments we compare the proposed system with DIVA for Rhino, a Radiance-based tool that uses conventional 2D-displays. The results show that RadVR can provide promising assistance in spatial understanding tasks, navigation, and sun position analysis in virtual reality.
Cascade Attention Guided Residue Learning GAN for Cross-Modal Translation
Venue: arXiv cs.CV 2021
Year: 2021

Since we were babies, we intuitively develop the ability to correlate the input from different cognitive sensors such as vision, audio, and text. However, in machine learning, this cross-modal learning is a nontrivial task because different modalities have no homogeneous properties. Previous works discover that there should be bridges among different modalities. From neurology and psychology perspective, humans have the capacity to link one modality with another one, e.g., associating a picture of a bird with the only hearing of its singing and vice versa. Is it possible for machine learning algorithms to recover the scene given the audio signal? In this paper, we propose a novel Cascade Attention-Guided Residue GAN (CAR-GAN), aiming at reconstructing the scenes given the corresponding audio signals. Particularly, we present a residue module to mitigate the gap between different modalities progressively. Moreover, a cascade attention guided network with a novel classification loss function is designed to tackle the cross-modal learning task. Our model keeps the consistency in high-level semantic label domain and is able to balance two different modalities. The experimental results demonstrate that our model achieves the state-of-the-art cross-modal audio-visual generation on the challenging Sub-URMP dataset. Code will be available at https://github.com/tuffr5/CAR-GAN.
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
Venue: arXiv cs.FL 2021
Year: 2021

The state complexity of a finite(-state) automaton intuitively measures the size of the description of the automaton. Sakoda and Sipser [STOC 1972, pp. 275--286] were concerned with nonuniform families of finite automata and they discussed the behaviors of the nonuniform complexity classes defined by such families of finite automata having polynomial-size state complexity. In a similar fashion, we introduce nonuniform state complexity classes using nonuniform families of quantum finite automata empowered by the flexible use of garbage tapes. We first present general inclusion and separation relationships among nonuniform state complexity classes of various one-way finite automata, including deterministic, nondeterministic, probabilistic, and quantum finite automata having polynomially many inner states. For two-way quantum finite automata equipped with flexible garbage tapes, we show a close relationship between the nonuniform state complexity of the family of such polynomial-size quantum finite automata and the parameterized complexity class induced by logarithmic-space quantum computation assisted by polynomial-size advice. We further establish a direct connection between space-bounded quantum computation with quantum advice and quantum finite automata whose transitions are dictated by superpositions of transition tables.
Fast and Simple Edge-Coloring Algorithms
Venue: arXiv cs.DS 2021
Year: 2021

We develop sequential algorithms for constructing edge-colorings of graphs and multigraphs efficiently and using few colors. Our primary focus is edge-coloring arbitrary simple graphs using $d+1$ colors, where $d$ is the largest vertex degree in the graph. Vizing's Theorem states that every simple graph can be edge-colored using $d+1$ colors. Although some graphs can be edge-colored using only $d$ colors, it is NP-hard to recognize graphs of this type [Holyer, 1981]. So using $d+1$ colors is a natural goal. Efficient techniques for $(d+1)$-edge-coloring were developed by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985, and independently by Arjomandi in 1982, leading to algorithms that run in $O(|E| \sqrt{|V| \log |V|})$ time. They have remained the fastest known algorithms for this task. We improve the runtime to $O(|E| \sqrt{|V|})$ with a small modification and careful analysis. We then develop a randomized version of the algorithm that is much simpler to implement and has the same asymptotic runtime, with very high probability. On the way to these results, we give a simple algorithm for $(2d-1)$-edge-coloring of multigraphs that runs in $O(|E|\log d)$ time. Underlying these algorithms is a general edge-coloring strategy which may lend itself to further applications.
An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
Venue: arXiv cs.GT 2021
Year: 2021

In this paper, we consider the problem of how to fairly dividing $m$ indivisible chores among $n$ agents. The fairness measure we considered here is the maximin share. The previous best known result is that there always exists a $\frac{4}{3}$ approximation maximin share allocation. With a novel algorithm, we can always find a $\frac{11}{9}$ approximation maximin share allocation for any instances. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem.
Markov Decision Process for MOOC users behavioral inference
Venue: arXiv cs.LG 2021
Year: 2021

Studies on massive open online courses (MOOCs) users discuss the existence of typical profiles and their impact on the learning process of the students. However defining the typical behaviors as well as classifying the users accordingly is a difficult task. In this paper we suggest two methods to model MOOC users behaviour given their log data. We mold their behavior into a Markov Decision Process framework. We associate the user's intentions with the MDP reward and argue that this allows us to classify them.
Preselection Bandits
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we introduce the Preselection Bandit problem, in which the learner preselects a subset of arms (choice alternatives) for a user, which then chooses the final arm from this subset. The learner is not aware of the user's preferences, but can learn them from observed choices. In our concrete setting, we allow these choices to be stochastic and model the user's actions by means of the Plackett-Luce model. The learner's main task is to preselect subsets that eventually lead to highly preferred choices. To formalize this goal, we introduce a reasonable notion of regret and derive lower bounds on the expected regret. Moreover, we propose algorithms for which the upper bound on expected regret matches the lower bound up to a logarithmic term of the time horizon.
Quasipolynomial Computation of Nested Fixpoints
Venue: arXiv cs.CC 2021
Year: 2021

It is well-known that the winning region of a parity game with $n$ nodes and $k$ priorities can be computed as a $k$-nested fixpoint of a suitable function; straightforward computation of this nested fixpoint requires $\mathcal{O}(n^{\frac{k}{2}})$ iterations of the function. Calude et al.'s recent quasipolynomial-time parity game solving algorithm essentially shows how to compute the same fixpoint in only quasipolynomially many iterations by reducing parity games to quasipolynomially sized safety games. Universal graphs have been used to modularize this transformation of parity games to equivalent safety games that are obtained by combining the original game with a universal graph. We show that this approach naturally generalizes to the computation of solutions of systems of \emph{any} fixpoint equations over finite lattices; hence, the solution of fixpoint equation systems can be computed by quasipolynomially many iterations of the equations. We present applications to modal fixpoint logics and games beyond relational semantics. For instance, the model checking problems for the energy $μ$-calculus, finite latticed $μ$-calculi, and the graded and the (two-valued) probabilistic $μ$-calculus -- with numbers coded in binary -- can be solved via nested fixpoints of functions that differ substantially from the function for parity games but still can be computed in quasipolynomial time; our result hence implies that model checking for these $μ$-calculi is in QP. Moreover, we improve the exponent in known exponential bounds on satisfiability checking.
Measuring Scientific Brain Drain with Hubs and Authorities: a Dual Perspective
Venue: arXiv cs.SI 2021
Year: 2021

In this work we study international migrations of researchers, scientists, and academics from a complex-network perspective to identify the central countries involved in the migration phenomenon. We define the scientific migration network (SMN) as temporal directed weighted network where nodes are world countries, links account for the number of scientists moving from one country to another, and timestamps represent years (from 2000 to 2016). 2.8 millions ORCID public profiles are utilized as data source. We then characterize hubs and authorities of the SMN employing the well-know weighted hyperlink-induced topic search (HITS) algorithm to catch the interplay between providing and attracting researchers from a global perspective, and relate these results to other local and global methodologies. We also investigate the local characteristics of successors of hubs and predecessors of authorities to dive deeper into the motivations that establish hubs and authorities as such. Our findings highlight the presence of a set of countries acting both as hubs and authorities, occupying a privileged position in the scientific migration network, and having similar local characteristics. Finally, we showcase how to employ network visualization to evince temporal evolutions of ego-networks of selected hubs and authorities.
HITS hits art
Venue: arXiv cs.CY 2021
Year: 2021

The blockchain art market is partitioned around the roles of artists and collectors and highly concentrated among few prominent figures. We hence propose to adapt Kleinberg's authority/hub HITS method to rate artists and collectors in the art context. This seems a reasonable choice since the original method deftly defines its scores in terms of a mutual recursive relationship between authorities/artists - the miners of information/art, and hubs/collectors - the assemblers of such information/art. We evaluated the proposed method on the collector-artist network of SuperRare gallery, the major crypto art marketplace. We found that the proposed artist and collector metrics are weakly correlated with other network science metrics like degree and strength. This hints the possibility of coupling different measures in order to profile active users of the gallery and suggests investment strategies with different risk/reward ratios for collectors as well as marketing strategies with different targets for artists.
Linear-semiorders and their incomparability graphs
Venue: arXiv cs.DM 2021
Year: 2021

A linear-interval order is the intersection of a linear order and an interval order. For this class of orders, several structural results have been known. This paper introduces a new subclass of linear-interval orders. We call a partial order a \emph{linear-semiorder} if it is the intersection of a linear order and a semiorder. We show a characterization and a polynomial-time recognition algorithm for linear-semiorders. We also prove that being a linear-semiorder is a comparability invariant, showing that incomparability graphs of linear-semiorders can be recognized in polynomial time.