OpenRaiser/Intern-Atlas huggingface dataset:
Neighborhood Spatial Aggregation MC Dropout for Efficient Uncertainty-aware Semantic Segmentation in Point Clouds
Venue: arXiv cs.CV 2021
Year: 2021

Uncertainty-aware semantic segmentation of the point clouds includes the predictive uncertainty estimation and the uncertainty-guided model optimization. One key challenge in the task is the efficiency of point-wise predictive distribution establishment. The widely-used MC dropout establishes the distribution by computing the standard deviation of samples using multiple stochastic forward propagations, which is time-consuming for tasks based on point clouds containing massive points. Hence, a framework embedded with NSA-MC dropout, a variant of MC dropout, is proposed to establish distributions in just one forward pass. Specifically, the NSA-MC dropout samples the model many times through a space-dependent way, outputting point-wise distribution by aggregating stochastic inference results of neighbors. Based on this, aleatoric and predictive uncertainties acquire from the predictive distribution. The aleatoric uncertainty is integrated into the loss function to penalize noisy points, avoiding the over-fitting of the model to some degree. Besides, the predictive uncertainty quantifies the confidence degree of predictions. Experimental results show that our framework obtains better segmentation results of real-world point clouds and efficiently quantifies the credibility of results. Our NSA-MC dropout is several times faster than MC dropout, and the inference time does not establish a coupling relation with the sampling times. The code will be available if the paper is accepted.
Using Hybrid Scheduling Algorithms for Solving Blockchain Allocation on Cloud
Venue: arXiv cs.DC 2021
Year: 2021

Companies are rushing to deliver their services and solutions through the cloud. The scheduling process is very critical in reducing delays. Scheduling also has a role in accessing resources without excessive waiting time. All this in context of modern advances in infrastructure and the emergence of Blockchain-as-a-service. What if integration is done between a hybrid scheduling algorithm and blockchain technology via the cloud. This integration aims to enhance and provide the service uninterruptedly. This method is distinguished, compared to other scheduling algorithms such as shortest-job-first and priority scheduling, that it does not suffer from starvation and it has a balanced load on resources. Based on analytical performance, the proposed hybrid scheduling has the markable result.
Vehicular Visible Light Communications for Automated Valet Parking
Venue: arXiv cs.NI 2021
Year: 2021

Visible light communication (VLC) is a promising Optical Wireless Communications (OWC) scheme that is demonstrated to provide secure, line-of-sight (LoS), and short-distance vehicle-to-vehicle (V2V) and vehicle-to-infrastructure(V2I) communications. Recently, automated driving applications, supported by V2I links are proposed to increase the reliability of the autonomous vehicles. To this regard, we propose a VLCbased V2I scheme to increase the V2I communication redundancy of autonomous valet parking (AVP) applications, through jam-free and location-based characteristics of VLC. In this paper, we demonstrate a novel architecture to support indoor parking-garage online-map update with vehicle on-board data transmissions and location-based map update dissemination through bidirectional VLC communications. The proposed system yields error-free LoS transmissions with Direct Current Biased Optical OFDM (DCO-OFDM) up to 33 m transmitter-receiver distance enabling vehicle CAN Bus data, infrastructure camera video, and LIDAR point cloud data sharing in an indoor parking garage.
T-Plots: A Novel Approach to Network Design
Venue: arXiv cs.NI 2021
Year: 2021

It is accepted wisdom that changes in the traffic matrix entail capacity over-provisioning, but there is no simple measure of just how much over-provisioning can buy. In this Thesis, we aim to provide the network designer with a simple view of the network robustness to traffic matrix changes. We first present the Traffic Load Distribution Plots, or T-Plots, a class of plots illustrating the percentage of traffic matrices that can be serviced as a function of the capacity over-provisioning. For instance, from a simple look at their T- Plots, network designers can guarantee that their network services all admissible traffic matrices, or 99% of permutation traffic matrices, or all traffic matrices with ingress/egress load at most half the maximum. We further show that, unfortunately, in the general case plotting T-Plots is #P-Complete, i.e., that it is impossible to plot a T-plot in a polynomial time by the noon tools. However, we show that T-Plots can sometimes be closely modeled as Gaussian, thus only using two values (mean and variance) to quantify the robustness of a capacity allocation to traffic matrix changes. We further utilize these Gaussian T-Plots to provide a more robust capacity allocation. Finally, we demonstrate the benefits of using T-Plots by showing results of extensive Monte Carlo simulations in a real backbone network. This Thesis was submitted in 2007. Since then, the results that appeared in it were applied in various networking environments. In this newer version, we revisit the results 13 years later and explain their relevance to state-of-the-art problems in network design.
Data driven design of optical resonators
Venue: arXiv cs.LG 2021
Year: 2021

Optical devices lie at the heart of most of the technology we see around us. When one actually wants to make such an optical device, one can predict its optical behavior using computational simulations of Maxwell's equations. If one then asks what the optimal design would be in order to obtain a certain optical behavior, the only way to go further would be to try out all of the possible designs and compute the electromagnetic spectrum they produce. When there are many design parameters, this brute force approach quickly becomes too computationally expensive. We therefore need other methods to create optimal optical devices. An alternative to the brute force approach is inverse design. In this paradigm, one starts from the desired optical response of a material and then determines the design parameters that are needed to obtain this optical response. There are many algorithms known in the literature that implement this inverse design. Some of the best performing, recent approaches are based on Deep Learning. The central idea is to train a neural network to predict the optical response for given design parameters. Since neural networks are completely differentiable, we can compute gradients of the response with respect to the design parameters. We can use these gradients to update the design parameters and get an optical response closer to the one we want. This allows us to obtain an optimal design much faster compared to the brute force approach. In my thesis, I use Deep Learning for the inverse design of the Fabry-Pérot resonator. This system can be described fully analytically and is therefore ideal to study.
Can Online Customer Reviews Help Design More Sustainable Products? A Preliminary Study on Amazon Climate Pledge Friendly Products
Venue: arXiv cs.CY 2021
Year: 2021

Online product reviews are a valuable resource for product developers to improve the design of their products. Yet, the potential value of customer feedback to improve the sustainability performance of products is still to be exploited. The present paper investigates and analyzes Amazon product reviews to bring new light on the following question: ``What sustainable design insights can be identified or interpreted from online product reviews?''. To do so, the top 100 reviews, evenly distributed by star ratings, for three product categories (laptop, printer, cable) are collected, manually annotated, analyzed and interpreted. For each product category, the reviews of two similar products (one with environmental certification and one standard version) are compared and combined to come up with sustainable design solutions. In all, for the six products considered, between 12% and 20% of the reviews mentioned directly or indirectly aspects or attributes that could be exploited to improve the design of these products from a sustainability perspective. Concrete examples of sustainable design leads that could be elicited from product reviews are given and discussed. As such, this contribution provides a baseline for future work willing to automate this process to gain further insights from online product reviews. Notably, the deployment of machine learning tools and the use of natural language processing techniques to do so are discussed as promising lines for future research.
Average-Case Complexity
Venue: arXiv cs.CC 2021
Year: 2021

We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect to all samplable distributions. Applying the theory to natural distributional problems remain an outstanding open question. We review some natural distributional problems whose average-case complexity is of particular interest and that do not yet fit into this theory. A major open question whether the existence of hard-on-average problems in NP can be based on the P$\neq$NP assumption or on related worst-case assumptions. We review negative results showing that certain proof techniques cannot prove such a result. While the relation between worst-case and average-case complexity for general NP problems remains open, there has been progress in understanding the relation between different "degrees" of average-case complexity. We discuss some of these "hardness amplification" results.
Deterministic Integer Factorization Algorithms
Venue: arXiv cs.DS 2022
Year: 2022

A new integer deterministic factorization algorithm, rated at arithmetic operations to $O(N^{1/6+\varepsilon})$ arithmetic operations, is presented in this note. Equivalently, given the least $(\log N)/6$ bits of a factor of the balanced integer $N = pq$, where $p$ and $q$ are primes, the algorithm factors the integer in polynomial time $O(\log(N)^c)$, with $c \geq 0$ constant, and $\varepsilon > 0$ an arbitrarily small number. It improves the current deterministic factorization algorithm, rated at arithmetic operations to $O(N^{1/5+\varepsilon})$ arithmetic operations.
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings
Venue: arXiv cs.DS 2022
Year: 2022

We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings. Most significantly, we explore adaptive interactive communication where the communicating parties decide who should speak next based on the history of the interaction. Braverman and Rao [STOC'11] show that non-adaptively one can code for any constant error rate below 1/4 but not more. They asked whether this bound could be improved using adaptivity. We answer this open question in the affirmative (with a slightly different collection of resources): Our adaptive coding scheme tolerates any error rate below 2/7 and we show that tolerating a higher error rate than 1/3 is impossible. We also show that in the setting of Franklin et al. [CRYPTO'13], where parties share randomness not known to the adversary, adaptivity increases the tolerable error rate from 1/2 to 2/3. For list-decodable interactive communications, where each party outputs a constant size list of possible outcomes, the tight tolerable error rate is 1/2. Our negative results hold even for unbounded communication and computations, whereas for our positive results communication and computations are polynomially bounded. Most prior work considered coding schemes with linear amount of communication, while allowing unbounded computations. We argue that studying tolerable error rates in this relaxed context helps to identify a setting's intrinsic optimal error rate. We set forward a strong working hypothesis which stipulates that for any setting the maximum tolerable error rate is independent of many computational and communication complexity measures. We believe this hypothesis to be a powerful guideline for the design of simple, natural, and efficient coding schemes and for understanding the (im)possibilities of coding for interactive communications.
Submixing and Shift-invariant Stochastic Games
Venue: arXiv cs.GT 2022
Year: 2022

We consider zero-sum stochastic games with perfect information and finitely many states and actions. The payoff is computed by a function which associates to each infinite sequence of states and actions a real number. We prove that if the payoff function is both shift-invariant and submixing, then the game is half-positional, i.e. the first player has an optimal strategy which is both deterministic and stationary. This result relies on the existence of epsilon-subgame-perfect strategies in shift-invariant games, a second contribution of the paper. The techniques can be used to establish a third result: for shift-invariant and submixing payoff functions, the existence of finite-memory strategies for player 2 in one-player games implies the same property for two-player games as well.
Implicational Relevance Logic is 2-EXPTIME-Complete
Venue: arXiv cs.LO 2022
Year: 2022

We show that provability in the implicational fragment of relevance logic is complete for doubly exponential time, using reductions to and from coverability in branching vector addition systems.
Data driven weak universal consistency
Venue: arXiv cs.IT 2022
Year: 2022

Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. But rich model classes may be too complex to admit estimators that converge to the truth with convergence rates that can be uniformly bounded over the entire collection of probability distributions comprising the model class, i.e. it may be impossible to guarantee uniform consistency of such estimators as the sample size increases. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the serious drawback that estimator performance is a function of the unknown model within the model class that is being estimated, and is therefore unknown. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. Departing from the classical uniform/pointwise consistency dichotomy that leads to this impasse, a new analysis framework is explored by studying rich model classes that may only admit pointwise consistency guarantees, yet all the information about the unknown model driving the observations that is needed to gauge estimator accuracy can be inferred from the sample at hand. We expect that this data-derived estimation framework will be broadly applicable to a wide range of estimation problems by providing a methodology to deal with much richer model classes. In this paper we analyze the lossless compression problem in detail in this novel data-derived framework.
The Directed Grid Theorem
Venue: arXiv cs.DM 2022
Year: 2022

The grid theorem, originally proved by Robertson and Seymour in Graph Minors V in 1986, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance in bidimensionality theory, and it is the basis for several other structure theorems developed in the graph minors project. In the mid-90s, Reed and Johnson, Robertson, Seymour and Thomas (see [Reed 97, Johnson, Robertson, Seymour, Thomas 01]), independently, conjectured an analogous theorem for directed graphs, i.e. the existence of a function f : N -> N such that every digraph of directed tree-width at least f(k) contains a directed grid of order k. In an unpublished manuscript from 2001, Johnson, Robertson, Seymour and Thomas give a proof of this conjecture for planar digraphs. But for over a decade, this was the most general case proved for the Reed, Johnson, Robertson, Seymour and Thomas conjecture. Only very recently, this result has been extended to all classes of digraphs excluding a fixed undirected graph as a minor (see [Kawarabayashi, Kreutzer 14]). In this paper, nearly two decades after the conjecture was made, we are finally able to confirm the Reed, Johnson, Robertson, Seymour and Thomas conjecture in full generality and to prove the directed grid theorem. As consequence of our results we are able to improve results in Reed et al. in 1996 [Reed, Robertson, Seymour, Thomas 96] (see also [Open Problem Garden]) on disjoint cycles of length at least l and in [Kawarabayashi, Kobayashi, Kreutzer 14] on quarter-integral disjoint paths. We expect many more algorithmic results to follow from the grid theorem.
Generalized solution for the Herman Protocol Conjecture
Venue: arXiv cs.DS 2022
Year: 2022

The Herman Protocol Conjecture states that the expected time $\mathbb{E}(\mathbf{T})$ of Herman's self-stabilizing algorithm in a system consisting of $N$ identical processes organized in a ring holding several tokens is at most $\frac{4}{27}N^{2}$. We prove the conjecture in its standard unbiased and also in a biased form for discrete processes, and extend the result to further variants where the tokens move via certain Lévy processes. Moreover, we derive a bound on the expected value of $\mathbb{E}(α^{\mathbf{T}})$ for all $1\leq α\leq (1-\varepsilon)^{-1}$ with a specific $\varepsilon>0$. Subject to the correctness of an optimization result that can be demonstrated empirically, all these estimations attain their maximum on the initial state with three tokens distributed equidistantly on the ring of $N$ processes. Such a relation is the symptom of the fact that both $\mathbb{E}(\mathbf{T})$ and $\mathbb{E}(α^{\mathbf{T}})$ are weighted sums of the probabilities $\mathbb{P}(\mathbf{T}\geq t)$.
The solvability of consensus in iterated models extended with safe-consensus
Venue: arXiv cs.DC 2022
Year: 2022

The safe-consensus task was introduced by Afek, Gafni and Lieber (DISC' 09) as a weakening of the classic consensus. When there is concurrency, the consensus output can be arbitrary, not even the input of any process. They showed that safe-consensus is equivalent to consensus, in a wait-free system. We study the solvability of consensus in three shared memory iterated models extended with the power of safe-consensus black boxes. In the first iterated model, for the $i$-th iteration, the processes write to memory, then they snapshot it and finally they invoke safe-consensus boxes. We prove that in this model, consensus cannot be implemented. In a second iterated model, processes first invoke safe-consensus, then they write to memory and finally they snapshot it. We show that this model is equivalent to the previous model and thus consensus cannot be implemented. In the last iterated model, processes write to the memory, invoke safe-consensus boxes and finally they snapshot the memory. We show that in this model, any wait-free implementation of consensus requires $\binom{n}{2}$ safe-consensus black-boxes and this bound is tight.
The Prose Storyboard Language: A Tool for Annotating and Directing Movies
Venue: arXiv cs.GR 2022
Year: 2022

The prose storyboard language is a formal language for describing movies shot by shot, where each shot is described with a unique sentence. The language uses a simple syntax and limited vocabulary borrowed from working practices in traditional movie-making, and is intended to be readable both by machines and humans. The language is designed to serve as a high-level user interface for intelligent cinematography and editing systems.
The role of twins in computing planar supports of hypergraphs
Venue: arXiv cs.DM 2022
Year: 2022

A support or realization of a hypergraph $H$ is a graph $G$ on the same vertex as $H$ such that for each hyperedge of $H$ it holds that its vertices induce a connected subgraph of $G$. The NP-hard problem of finding a planar support has applications in hypergraph drawing and network design. Previous algorithms for the problem assume that twins -- pairs of vertices that are in precisely the same hyperedges -- can safely be removed from the input hypergraph. We prove that this assumption is generally wrong, yet that the number of twins necessary for a hypergraph to have a planar support only depends on its number of hyperedges. We give an explicit upper bound on the number of twins necessary for a hypergraph with $m$ hyperedges to have an $r$-outerplanar support, which depends only on $r$ and $m$. Since all additional twins can be safely removed, we obtain a linear-time algorithm for computing $r$-outerplanar supports for hypergraphs with $m$ hyperedges if $m$ and $r$ are constant; in other words, the problem is fixed-parameter linear-time solvable with respect to the parameters $m$ and $r$.
Open-Set Support Vector Machines
Venue: arXiv cs.LG 2022
Year: 2022

Often, when dealing with real-world recognition problems, we do not need, and often cannot have, knowledge of the entire set of possible classes that might appear during operational testing. In such cases, we need to think of robust classification methods able to deal with the "unknown" and properly reject samples belonging to classes never seen during training. Notwithstanding, existing classifiers to date were mostly developed for the closed-set scenario, i.e., the classification setup in which it is assumed that all test samples belong to one of the classes with which the classifier was trained. In the open-set scenario, however, a test sample can belong to none of the known classes and the classifier must properly reject it by classifying it as unknown. In this work, we extend upon the well-known Support Vector Machines (SVM) classifier and introduce the Open-Set Support Vector Machines (OSSVM), which is suitable for recognition in open-set setups. OSSVM balances the empirical risk and the risk of the unknown and ensures that the region of the feature space in which a test sample would be classified as known (one of the known classes) is always bounded, ensuring a finite risk of the unknown. In this work, we also highlight the properties of the SVM classifier related to the open-set scenario, and provide necessary and sufficient conditions for an RBF SVM to have bounded open-space risk.
Learning Robust Features for Gait Recognition by Maximum Margin Criterion
Venue: arXiv cs.CV 2022
Year: 2022

In the field of gait recognition from motion capture data, designing human-interpretable gait features is a common practice of many fellow researchers. To refrain from ad-hoc schemes and to find maximally discriminative features we may need to explore beyond the limits of human interpretability. This paper contributes to the state-of-the-art with a machine learning approach for extracting robust gait features directly from raw joint coordinates. The features are learned by a modification of Linear Discriminant Analysis with Maximum Margin Criterion so that the identities are maximally separated and, in combination with an appropriate classifier, used for gait recognition. Experiments on the CMU MoCap database show that this method outperforms eight other relevant methods in terms of the distribution of biometric templates in respective feature spaces expressed in four class separability coefficients. Additional experiments indicate that this method is a leading concept for rank-based classifier systems.