OpenRaiser/Intern-Atlas huggingface dataset:
A Tight Max-Flow Min-Cut Duality Theorem for Non-Linear Multicommodity Flows
Venue: arXiv cs.DS 2024
Year: 2024

The Max-Flow Min-Cut theorem is the classical duality result for the Max-Flow problem, which considers flow of a single commodity. We study a multiple commodity generalization of Max-Flow in which flows are composed of real-valued k-vectors through networks with arc capacities formed by regions in \R^k. Given the absence of a clear notion of ordering in the multicommodity case, we define the generalized max flow as the feasible region of all flow values. We define a collection of concepts and operations on flows and cuts in the multicommodity setting. We study the mutual capacity of a set of cuts, defined as the set of flows that can pass through all cuts in the set. We present a method to calculate the mutual capacity of pairs of cuts, and then generalize the same to a method of calculation for arbitrary sets of cuts. We show that the mutual capacity is exactly the set of feasible flows in the network, and hence is equal to the max flow. Furthermore, we present a simple class of the multicommodity max flow problem where computations using this tight duality result could run significantly faster than default brute force computations. We also study more tractable special cases of the multicommodity max flow problem where the objective is to transport a maximum real or integer multiple of a given vector through the network. We devise an augmenting cycle search algorithm that reduces the optimization problem to one with m constraints in at most \R^{(m-n+1)k} space from one that requires mn constraints in \R^{mk} space for a network with n nodes and m edges. We present efficient algorithms that compute eps-approximations to both the ratio and the integer ratio maximum flow problems.
An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
Venue: arXiv cs.LO 2024
Year: 2024

An algorithm for reversible logic synthesis is proposed. The task is, for a given $n$-bit substitution map $P_n: \{0,1\}^n \rightarrow \{0,1\}^n$, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates denoted by $C^m\!X$, where $m$ is the number of control bits that ranges from 0 to $n-1$. Controlled gates with large $m \,\,(>2)$ are then further decomposed into $C^0\!X$, $C^1\!X$, and $C^2\!X$ gates. A primary concern in designing the algorithm is to reduce the use of $C^2\!X$ gate (also known as Toffoli gate) which is known to be universal. The main idea is to view an $n$-bit substitution map as a rank-$2n$ tensor and to transform it such that the resulting map can be written as a tensor product of a rank-($2n-2$) tensor and the $2\times 2$ identity matrix. Let $\mathcal{P}_n$ be a set of all $n$-bit substitution maps. What we try to find is a size reduction map $\mathcal{A}_{\rm red}: \mathcal{P}_n \rightarrow \{P_n: P_n = P_{n-1} \otimes I_2\}$. %, where $I_m$ is the $m\times m$ identity matrix. One can see that the output $P_{n-1} \otimes I_2$ acts nontrivially on $n-1$ bits only, meaning that the map to be synthesized becomes $P_{n-1}$. The size reduction process is iteratively applied until it reaches tensor product of only $2 \times 2$ matrices.
Minimal Session Types for the $π$-calculus (Extended Version)
Venue: arXiv cs.PL 2024
Year: 2024

Session types are a discipline for the static verification of message-passing programs. A session type specifies a channel's protocol as sequences of exchanges. It is most relevant to investigate session-based concurrency by identifying the essential notions that enable program specification and verification. Following that perspective, prior work identified minimal session types (MSTs), a sub-class of session types without the sequentiality construct, which specifies the structure of communication actions. This formulation of session types led to establish a minimality result: every process typable with standard session types can be compiled down to a process typable using MSTs, which mimics sequentiality in types via additional process synchronizations. Such a minimality result is significant because it justifies session types in terms of themselves, without resorting to external notions; it was proven for a higher-order session pi-calculus, in which values are abstractions (functions from names to processes). In this paper, we study MSTs and their associated minimality result but now for the session pi-calculus, the (first-order) language in which values are names and for which session types have been more widely studied. We first show that this new minimality result can be obtained by composing known results. Then, we develop optimizations of this new minimality result and prove that the associated transformation into processes with MSTs satisfies dynamic correctness.
Generalisations of Matrix Partitions : Complexity and Obstructions
Venue: arXiv cs.CC 2024
Year: 2024

A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or $\star$ (both an arc and a non-arc). In a series of papers, Hell and co-authors proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems, where arcs and non-arcs can be both mapped to $\star$-arcs, while a non-arc cannot be mapped to an arc, and vice-versa. Even though Matrix Partition Problems are generalisations of CSPs, they share with them the property of being ``intrinsically'' combinatorial. So, the question of a possible P-time vs NP-complete dichotomy is a very natural one and was raised in Hell et al.'s papers. We propose a generalisation of Matrix Partitions to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partitions are P-time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partitions on directed graphs are not P-time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partitions. We then turn our attention to Matrix Partitions that can be described by finite sets of (induced-subgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP-complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partitions as it is well-known that CSP is tractable on the class of trees.
MBDP: A Model-based Approach to Achieve both Robustness and Sample Efficiency via Double Dropout Planning
Venue: arXiv cs.LG 2024
Year: 2024

Model-based reinforcement learning is a widely accepted solution for solving excessive sample demands. However, the predictions of the dynamics models are often not accurate enough, and the resulting bias may incur catastrophic decisions due to insufficient robustness. Therefore, it is highly desired to investigate how to improve the robustness of model-based RL algorithms while maintaining high sampling efficiency. In this paper, we propose Model-Based Double-dropout Planning (MBDP) to balance robustness and efficiency. MBDP consists of two kinds of dropout mechanisms, where the rollout-dropout aims to improve the robustness with a small cost of sample efficiency, while the model-dropout is designed to compensate for the lost efficiency at a slight expense of robustness. By combining them in a complementary way, MBDP provides a flexible control mechanism to meet different demands of robustness and efficiency by tuning two corresponding dropout ratios. The effectiveness of MBDP is demonstrated both theoretically and experimentally.
How to avoid machine learning pitfalls: a guide for academic researchers
Venue: arXiv cs.LG 2024
Year: 2024

Mistakes in machine learning practice are commonplace, and can result in a loss of confidence in the findings and products of machine learning. This guide outlines common mistakes that occur when using machine learning, and what can be done to avoid them. Whilst it should be accessible to anyone with a basic understanding of machine learning techniques, it focuses on issues that are of particular concern within academic research, such as the need to do rigorous comparisons and reach valid conclusions. It covers five stages of the machine learning process: what to do before model building, how to reliably build models, how to robustly evaluate models, how to compare models fairly, and how to report results.
Conditional Separation as a Binary Relation. A Coq Assisted Proof
Venue: arXiv cs.DM 2024
Year: 2024

The concept of d-separation holds a pivotal role in causality theory, serving as a fundamental tool for deriving conditional independence properties from causal graphs. Pearl defined the d-separation of two subsets conditionally on a third one. In this study, we present a novel perspective by showing i) how the d-separation can be extended beyond acyclic graphs, possibly infinite, and ii) how it can be expressed and characterized as a binary relation between vertices. Compared to the typical perspectives in causality theory, our equivalence opens the door to more compact and computational proofing techniques, because the language of binary relations is well adapted to equational reasoning. Additionally, and of independent interest, the proofs of the results presented in this paper are checked with the Coq proof assistant.
A computational medical XR discipline
Venue: arXiv cs.GR 2024
Year: 2024

Computational Medical Extended Reality (CMXR), brings together life sciences and neuroscience with mathematics, engineering and computer science. It unifies computational science (scientific computing) with intelligent extended reality and spatial computing for the medical field. It significantly differs from previous "Clinical XR" or "Medical XR" terms, as it is focusing on how to integrate computational methods from neural simulation to computational geometry, computational vision and computer graphics with deep learning models to solve specific hard problems in medicine and neuroscience: from low/no-code/genAI authoring platforms to deep learning XR systems for training, planning, operative navigation, therapy and rehabilitation.
Order Optimal Bounds for One-Shot Federated Learning over non-Convex Loss Functions
Venue: arXiv cs.LG 2024
Year: 2024

We consider the problem of federated learning in a one-shot setting in which there are $m$ machines, each observing $n$ sample functions from an unknown distribution on non-convex loss functions. Let $F:[-1,1]^d\to\mathbb{R}$ be the expected loss function with respect to this unknown distribution. The goal is to find an estimate of the minimizer of $F$. Based on its observations, each machine generates a signal of bounded length $B$ and sends it to a server. The server collects signals of all machines and outputs an estimate of the minimizer of $F$. We show that the expected loss of any algorithm is lower bounded by $\max\big(1/(\sqrt{n}(mB)^{1/d}), 1/\sqrt{mn}\big)$, up to a logarithmic factor. We then prove that this lower bound is order optimal in $m$ and $n$ by presenting a distributed learning algorithm, called Multi-Resolution Estimator for Non-Convex loss function (MRE-NC), whose expected loss matches the lower bound for large $mn$ up to polylogarithmic factors.
Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioning
Venue: arXiv cs.LG 2024
Year: 2024

We consider federated learning in tiered communication networks. Our network model consists of a set of silos, each holding a vertical partition of the data. Each silo contains a hub and a set of clients, with the silo's vertical data shard partitioned horizontally across its clients. We propose Tiered Decentralized Coordinate Descent (TDCD), a communication-efficient decentralized training algorithm for such two-tiered networks. The clients in each silo perform multiple local gradient steps before sharing updates with their hub to reduce communication overhead. Each hub adjusts its coordinates by averaging its workers' updates, and then hubs exchange intermediate updates with one another. We present a theoretical analysis of our algorithm and show the dependence of the convergence rate on the number of vertical partitions and the number of local updates. We further validate our approach empirically via simulation-based experiments using a variety of datasets and objectives.
OpenStreetMap-based Autonomous Navigation With LiDAR Naive-Valley-Path Obstacle Avoidance
Venue: arXiv cs.RO 2024
Year: 2024

OpenStreetMaps (OSM) is currently studied as the environment representation for autonomous navigation. It provides advantages such as global consistency, a heavy-less map construction process, and a wide variety of road information publicly available. However, the location of this information is usually not very accurate locally. In this paper, we present a complete autonomous navigation pipeline using OSM information as environment representation for global planning. To avoid the flaw of local low-accuracy, we offer the novel LiDAR-based Naive-Valley-Path (NVP) method that exploits the concept of "valley" areas to infer the local path always furthest from obstacles. This behavior allows navigation always through the center of trafficable areas following the road's shape independently of OSM error. Furthermore, NVP is a naive method that is highly sample-time-efficient. This time efficiency also enables obstacle avoidance, even for dynamic objects. We demonstrate the system's robustness in our research platform BLUE, driving autonomously across the University of Alicante Scientific Park for more than 20 km with 0.24 meters of average error against the road's center with a 19.8 ms of average sample time. Our vehicle avoids static obstacles in the road and even dynamic ones, such as vehicles and pedestrians.
Boolean proportions
Venue: arXiv cs.AI 2024
Year: 2024

The author has recently introduced an abstract algebraic framework of analogical proportions within the general setting of universal algebra. This paper studies analogical proportions in the boolean domain consisting of two elements 0 and 1 within his framework. It turns out that our notion of boolean proportions coincides with two prominent models from the literature in different settings. This means that we can capture two separate modellings of boolean proportions within a single framework which is mathematically appealing and provides further evidence for the robustness and applicability of the general framework.
Smooth Surfaces via Nets of Geodesics
Venue: arXiv cs.CG 2024
Year: 2024

The goal of this study is to provide a method for computing the following: Given a network of curves in 3d (satisfying a condition at the intersection points), compute efficiently a smooth surface such that the curves are geodesics on it. This work can serve as a base for engineers who wish to implement computations of such surfaces in Computer Aided Design (CAD) software or other applications. The motivation for this study was the following hypothesis and observation together with the desire to improve CAD interfaces. The hypothesis and observation is that artists draw projections of geodesics to illustrate 3d objects: for example projections of nets of curves can be seen in drawings of Rembrandt. In addition, this observation is supported by research in cognitive sciences: in a seminal work by the late David Knill he suggested that the human visual system incorporates a geodesic constraint in the processing of reflected contours.
A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we propose Posterior Sampling Reinforcement Learning for Zero-sum Stochastic Games (PSRL-ZSG), the first online learning algorithm that achieves Bayesian regret bound of $O(HS\sqrt{AT})$ in the infinite-horizon zero-sum stochastic games with average-reward criterion. Here $H$ is an upper bound on the span of the bias function, $S$ is the number of states, $A$ is the number of joint actions and $T$ is the horizon. We consider the online setting where the opponent can not be controlled and can take any arbitrary time-adaptive history-dependent strategy. Our regret bound improves on the best existing regret bound of $O(\sqrt[3]{DS^2AT^2})$ by Wei et al. (2017) under the same assumption and matches the theoretical lower bound in $T$.
Open-World Distributed Robot Self-Localization with Transferable Visual Vocabulary and Both Absolute and Relative Features
Venue: arXiv cs.CV 2024
Year: 2024

Visual robot self-localization is a fundamental problem in visual robot navigation and has been studied across various problem settings, including monocular and sequential localization. However, many existing studies focus primarily on single-robot scenarios, with limited exploration into general settings involving diverse robots connected through wireless networks with constrained communication capacities, such as open-world distributed robot systems. In particular, issues related to the transfer and sharing of key knowledge, such as visual descriptions and visual vocabulary, between robots have been largely neglected. This work introduces a new self-localization framework designed for open-world distributed robot systems that maintains state-of-the-art performance while offering two key advantages: (1) it employs an unsupervised visual vocabulary model that maps to multimodal, lightweight, and transferable visual features, and (2) the visual vocabulary itself is a lightweight and communication-friendly model. Although the primary focus is on encoding monocular view images, the framework can be easily extended to sequential localization applications. By utilizing complementary similarity-preserving features -- both absolute and relative -- the framework meets the requirements for being unsupervised, multimodal, lightweight, and transferable. All features are learned and recognized using a lightweight graph neural network and scene graph. The effectiveness of the proposed method is validated in both passive and active self-localization scenarios.
LAViTeR: Learning Aligned Visual and Textual Representations Assisted by Image and Caption Generation
Venue: arXiv cs.CV 2024
Year: 2024

Pre-training visual and textual representations from large-scale image-text pairs is becoming a standard approach for many downstream vision-language tasks. The transformer-based models learn inter and intra-modal attention through a list of self-supervised learning tasks. This paper proposes LAViTeR, a novel architecture for visual and textual representation learning. The main module, Visual Textual Alignment (VTA) will be assisted by two auxiliary tasks, GAN-based image synthesis and Image Captioning. We also propose a new evaluation metric measuring the similarity between the learnt visual and textual embedding. The experimental results on two public datasets, CUB and MS-COCO, demonstrate superior visual and textual representation alignment in the joint feature embedding space
Generalized Sweeping Line Spanners
Venue: arXiv cs.CG 2024
Year: 2024

We present sweeping line graphs, a generalization of $Θ$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
Venue: arXiv cs.NE 2024
Year: 2024

Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multi-objective formulation, we propose and analyze improved convex multi-objective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective and the improved convex multi-objective approach in practice.
High-Fidelity GAN Inversion for Image Attribute Editing
Venue: arXiv cs.CV 2024
Year: 2024

We present a novel high-fidelity generative adversarial network (GAN) inversion framework that enables attribute editing with image-specific details well-preserved (e.g., background, appearance, and illumination). We first analyze the challenges of high-fidelity GAN inversion from the perspective of lossy data compression. With a low bit-rate latent code, previous works have difficulties in preserving high-fidelity details in reconstructed and edited images. Increasing the size of a latent code can improve the accuracy of GAN inversion but at the cost of inferior editability. To improve image fidelity without compromising editability, we propose a distortion consultation approach that employs a distortion map as a reference for high-fidelity reconstruction. In the distortion consultation inversion (DCI), the distortion map is first projected to a high-rate latent map, which then complements the basic low-rate latent code with more details via consultation fusion. To achieve high-fidelity editing, we propose an adaptive distortion alignment (ADA) module with a self-supervised training scheme, which bridges the gap between the edited and inversion images. Extensive experiments in the face and car domains show a clear improvement in both inversion and editing quality.