OpenRaiser/Intern-Atlas huggingface dataset:
Solving Jigsaw Puzzles By the Graph Connection Laplacian
Venue: arXiv cs.CV 2020
Year: 2020

We propose a novel mathematical framework to address the problem of automatically solving large jigsaw puzzles. This problem assumes a large image, which is cut into equal square pieces that are arbitrarily rotated and shuffled, and asks to recover the original image given the transformed pieces. The main contribution of this work is a method for recovering the rotations of the pieces when both shuffles and rotations are unknown. A major challenge of this procedure is estimating the graph connection Laplacian without the knowledge of shuffles. A careful combination of our proposed method for estimating rotations with any existing method for estimating shuffles results in a practical solution for the jigsaw puzzle problem. Our theory guarantees, in a clean setting, that our basic idea of recovering rotations is robust to some corruption of the connection graph. Numerical experiments demonstrate the competitive accuracy of this solution, its robustness to corruption and, its computational advantage for large puzzles.
Spatter: A Tool for Evaluating Gather / Scatter Performance
Venue: arXiv cs.PF 2020
Year: 2020

This paper describes a new benchmark tool, Spatter, for assessing memory system architectures in the context of a specific category of indexed accesses known as gather and scatter. These types of operations are increasingly used to express sparse and irregular data access patterns, and they have widespread utility in many modern HPC applications including scientific simulations, data mining and analysis computations, and graph processing. However, many traditional benchmarking tools like STREAM, STRIDE, and GUPS focus on characterizing only uniform stride or fully random accesses despite evidence that modern applications use varied sets of more complex access patterns. Spatter is an open-source benchmark that provides a tunable and configurable framework to benchmark a variety of indexed access patterns, including variations of gather/scatter that are seen in HPC mini-apps evaluated in this work. The design of Spatter includes tunable backends for OpenMP and CUDA, and experiments show how it can be used to evaluate 1) uniform access patterns for CPU and GPU, 2) prefetching regimes for gather/scatter, 3) compiler implementations of vectorization for gather/scatter, and 4) trace-driven "proxy patterns" that reflect the patterns found in multiple applications. The results from Spatter experiments show that GPUs typically outperform CPUs for these operations, and that Spatter can better represent the performance of some cache-dependent mini-apps than traditional STREAM bandwidth measurements.
Resolving the Feedback Bottleneck of Multi-Antenna Coded Caching
Venue: arXiv cs.IT 2020
Year: 2020

Multi-antenna cache-aided wireless networks have been known to suffer from a severe feedback bottleneck, where achieving the maximal Degrees-of-Freedom (DoF) performance required feedback from all served users. These costs matched the caching gains and thus scaled with the number of users. In the context of the $L$-antenna MISO broadcast channel with $K$ receivers having normalized cache size $γ$, we pair a fundamentally novel algorithm together with a new information-theoretic converse, and identify the optimal tradeoff between feedback costs and DoF performance, by showing that having CSIT from only $C<L$ served users implies an optimal one-shot linear DoF of $C+Kγ$. As a side consequence of this, we also now understand that the well known DoF performance $L+Kγ$ is in fact exactly optimal. In practice, the above means that we are now able to disentangle caching gains from feedback costs, thus achieving unbounded caching gains at the mere feedback cost of the multiplexing gain. This further solidifies the role of caching in boosting multi-antenna systems; caching now can provide unbounded DoF gains over multi-antenna downlink systems, at no additional feedback costs. The above results are extended to also include the corresponding multiple transmitter scenario with caches at both ends.
Uncertainty relations and sparse signal recovery
Venue: arXiv cs.IT 2020
Year: 2020

This chapter provides a principled introduction to uncertainty relations underlying sparse signal recovery. We start with the seminal work by Donoho and Stark, 1989, which defines uncertainty relations as upper bounds on the operator norm of the band-limitation operator followed by the time-limitation operator, generalize this theory to arbitrary pairs of operators, and then develop -- out of this generalization -- the coherence-based uncertainty relations due to Elad and Bruckstein, 2002, as well as uncertainty relations in terms of concentration of $1$-norm or $2$-norm. The theory is completed with the recently discovered set-theoretic uncertainty relations which lead to best possible recovery thresholds in terms of a general measure of parsimony, namely Minkowski dimension. We also elaborate on the remarkable connection between uncertainty relations and the "large sieve", a family of inequalities developed in analytic number theory. It is finally shown how uncertainty relations allow to establish fundamental limits of practical signal recovery problems such as inpainting, declipping, super-resolution, and denoising of signals corrupted by impulse noise or narrowband interference. Detailed proofs are provided throughout the chapter.
Gauges, Loops, and Polynomials for Partition Functions of Graphical Models
Venue: arXiv cs.LG 2020
Year: 2020

Graphical models represent multivariate and generally not normalized probability distributions. Computing the normalization factor, called the partition function, is the main inference challenge relevant to multiple statistical and optimization applications. The problem is of an exponential complexity with respect to the number of variables. In this manuscript, aimed at approximating the PF, we consider Multi-Graph Models where binary variables and multivariable factors are associated with edges and nodes, respectively, of an undirected multi-graph. We suggest a new methodology for analysis and computations that combines the Gauge Function technique with the technique from the field of real stable polynomials. We show that the Gauge Function has a natural polynomial representation in terms of gauges/variables associated with edges of the multi-graph. Moreover, it can be used to recover the Partition Function through a sequence of transformations allowing appealing algebraic and graphical interpretations. Algebraically, one step in the sequence consists in application of a differential operator over gauges associated with an edge. Graphically, the sequence is interpreted as a repetitive elimination of edges resulting in a sequence of models on decreasing in size graphs with the same Partition Function. Even though complexity of computing factors in the sequence models grow exponentially with the number of eliminated edges, polynomials associated with the new factors remain bi-stable if the original factors have this property. Moreover, we show that Belief Propagation estimations in the sequence do not decrease, each low-bounding the Partition Function.
Estimation of urban traffic state with probe vehicles
Venue: arXiv cs.SY 2020
Year: 2020

We present in this paper a method to estimate urban traffic state with communicating vehicles. Vehicles moving on the links of the urban road network form queues at the traffic lights. We assume that a proportion of vehicles are equipped with localization and communication capabilities, and name them probe vehicles. First, we propose a method for the estimation of the penetration ratio of probe vehicles, as well as the vehicles arrival rate on a link. Moreover, we show that turn ratios at each junction can be estimated. Second, assuming that the turn ratios at each junction are given, we propose an estimation of the queue lengths on a 2-lanes link, by extending a 1-lane existing method. Our extension introduces vehicles assignment onto the lanes. Third, based on this approach, we propose optimal control laws for the traffic light and for the assignment of the arriving vehicles onto the lane queues. Finally, numerical simulations are conducted with Veins framework that bi-directionally couples microscopic road traffic and communication simulators. We illustrate and discuss our propositions with the simulation results.
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Venue: arXiv cs.DS 2020
Year: 2020

The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of $n$ leaves, defined as the number of subsets of four leaves related by a different topology in both trees. After a series of previous results, Brodal et al. [SODA 2013] presented an algorithm that computes this number in $\mathcal{O}(nd\log n)$ time, where $d$ is the maximum degree of a node. Our main contribution is a two-way reduction establishing that the complexity of computing the quartet distance between two trees on $n$ leaves is the same, up to polylogarithmic factors, as the complexity of counting 4-cycles in an undirected simple graph with $m$ edges. The latter problem has been extensively studied, and the fastest known algorithm by Vassilevska Williams [SODA 2015] works in $\mathcal{O}(m^{1.48})$ time. In fact, even for the seemingly simpler problem of detecting a 4-cycle, the best known algorithm works in $\mathcal{O}(m^{4/3})$ time, and a conjecture of Yuster and Zwick implies that this might be optimal. In particular, an almost-linear time for computing the quartet distance would imply a surprisingly efficient algorithm for counting 4-cycles. In the other direction, by plugging in the state-of-the-art algorithms for counting 4-cycles, our reduction allows us to significantly decrease the complexity of computing the quartet distance. For trees with unbounded degrees we obtain an $\mathcal{O}(n^{1.48})$ time algorithm, which is a substantial improvement on the previous bound of $\mathcal{O}(n^{2}\log n)$. For trees with degrees bounded by $d$, by analysing the reduction more carefully, we are able to obtain an $\mathcal{\tilde O}(nd^{0.77})$ time algorithm, which is again a nontrivial improvement on the previous bound of $\mathcal{O}(nd\log n)$.
Bayesian Cycle-Consistent Generative Adversarial Networks via Marginalizing Latent Sampling
Venue: arXiv cs.LG 2020
Year: 2020

Recent techniques built on Generative Adversarial Networks (GANs), such as Cycle-Consistent GANs, are able to learn mappings among different domains built from unpaired datasets, through min-max optimization games between generators and discriminators. However, it remains challenging to stabilize the training process and thus cyclic models fall into mode collapse accompanied by the success of discriminator. To address this problem, we propose an novel Bayesian cyclic model and an integrated cyclic framework for inter-domain mappings. The proposed method motivated by Bayesian GAN explores the full posteriors of cyclic model via sampling latent variables and optimizes the model with maximum a posteriori (MAP) estimation. Hence, we name it Bayesian CycleGAN. In addition, original CycleGAN cannot generate diversified results. But it is feasible for Bayesian framework to diversify generated images by replacing restricted latent variables in inference process. We evaluate the proposed Bayesian CycleGAN on multiple benchmark datasets, including Cityscapes, Maps, and Monet2photo. The proposed method improve the per-pixel accuracy by 15% for the Cityscapes semantic segmentation task within origin framework and improve 20% within the proposed integrated framework, showing better resilience to imbalance confrontation. The diversified results of Monet2Photo style transfer also demonstrate its superiority over original cyclic model. We provide codes for all of our experiments in https://github.com/ranery/Bayesian-CycleGAN.
On compact representations of Voronoi cells of lattices
Venue: arXiv cs.DS 2020
Year: 2020

In a seminal work, Micciancio & Voulgaris (2013) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be $c$-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by $c$ in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on $c$. Thus, our main focus is the behavior of the smallest possible value of $c$, with the following results: There always exist $c$-compact bases, where $c$ is bounded by $n^2$ for an $n$-dimension lattice; there are lattices not admitting a $c$-compact basis with $c$ growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a $1$-compact basis.
Goal-constrained Planning Domain Model Verification of Safety Properties
Venue: arXiv cs.AI 2020
Year: 2020

The verification of planning domain models is crucial to ensure the safety, integrity and correctness of planning-based automated systems. This task is usually performed using model checking techniques. However, unconstrained application of model checkers to verify planning domain models can result in false positives, i.e.counterexamples that are unreachable by a sound planner when using the domain under verification during a planning task. In this paper, we discuss the downside of unconstrained planning domain model verification. We then introduce the notion of a valid planning counterexample, and demonstrate how model checkers, as well as state trajectory constraints planning techniques, should be used to verify planning domain models so that invalid planning counterexamples are not returned.
Compact and Efficient Encodings for Planning in Factored State and Action Spaces with Learned Binarized Neural Network Transition Models
Venue: arXiv cs.AI 2020
Year: 2020

In this paper, we leverage the efficiency of Binarized Neural Networks (BNNs) to learn complex state transition models of planning domains with discretized factored state and action spaces. In order to directly exploit this transition structure for planning, we present two novel compilations of the learned factored planning problem with BNNs based on reductions to Weighted Partial Maximum Boolean Satisfiability (FD-SAT-Plan+) as well as Binary Linear Programming (FD-BLP-Plan+). Theoretically, we show that our SAT-based Bi-Directional Neuron Activation Encoding is asymptotically the most compact encoding relative to the current literature and supports Unit Propagation (UP) -- an important property that facilitates efficiency in SAT solvers. Experimentally, we validate the computational efficiency of our Bi-Directional Neuron Activation Encoding in comparison to an existing neuron activation encoding and demonstrate the ability to learn complex transition models with BNNs. We test the runtime efficiency of both FD-SAT-Plan+ and FD-BLP-Plan+ on the learned factored planning problem showing that FD-SAT-Plan+ scales better with increasing BNN size and complexity. Finally, we present a finite-time incremental constraint generation algorithm based on generalized landmark constraints to improve the planning accuracy of our encodings through simulated or real-world interaction.
MIST: Multiple Instance Spatial Transformer Network
Venue: arXiv cs.CV 2020
Year: 2020

We propose a deep network that can be trained to tackle image reconstruction and classification problems that involve detection of multiple object instances, without any supervision regarding their whereabouts. The network learns to extract the most significant top-K patches, and feeds these patches to a task-specific network -- e.g., auto-encoder or classifier -- to solve a domain specific problem. The challenge in training such a network is the non-differentiable top-K selection process. To address this issue, we lift the training optimization problem by treating the result of top-K selection as a slack variable, resulting in a simple, yet effective, multi-stage training. Our method is able to learn to detect recurrent structures in the training dataset by learning to reconstruct images. It can also learn to localize structures when only knowledge on the occurrence of the object is provided, and in doing so it outperforms the state-of-the-art.
Exploring Restart Distributions
Venue: arXiv cs.LG 2020
Year: 2020

We consider the generic approach of using an experience memory to help exploration by adapting a restart distribution. That is, given the capacity to reset the state with those corresponding to the agent's past observations, we help exploration by promoting faster state-space coverage via restarting the agent from a more diverse set of initial states, as well as allowing it to restart in states associated with significant past experiences. This approach is compatible with both on-policy and off-policy methods. However, a caveat is that altering the distribution of initial states could change the optimal policies when searching within a restricted class of policies. To reduce this unsought learning bias, we evaluate our approach in deep reinforcement learning which benefits from the high representational capacity of deep neural networks. We instantiate three variants of our approach, each inspired by an idea in the context of experience replay. Using these variants, we show that performance gains can be achieved, especially in hard exploration problems.
Multi-label classification search space in the MEKA software
Venue: arXiv cs.LG 2020
Year: 2020

This supplementary material aims to describe the proposed multi-label classification (MLC) search spaces based on the MEKA and WEKA softwares. First, we overview 26 MLC algorithms and meta-algorithms in MEKA, presenting their main characteristics, such as hyper-parameters, dependencies and constraints. Second, we review 28 single-label classification (SLC) algorithms, preprocessing algorithms and meta-algorithms in the WEKA software. These SLC algorithms were also studied because they are part of the proposed MLC search spaces. Fundamentally, this occurs due to the problem transformation nature of several MLC algorithms used in this work. These algorithms transform an MLC problem into one or several SLC problems in the first place and solve them with SLC model(s) in a next step. Therefore, understanding their main characteristics is crucial to this work. Finally, we present a formal description of the search spaces by proposing a context-free grammar that encompasses the 54 learning algorithms. This grammar basically comprehends the possible combinations, the constraints and dependencies among the learning algorithms.
Functional Analysis Attacks on Logic Locking
Venue: arXiv cs.CR 2020
Year: 2020

Logic locking refers to a set of techniques that can protect integrated circuits (ICs) from counterfeiting, piracy and malicious functionality changes by an untrusted foundry. It achieves these goals by introducing new inputs, called key inputs, and additional logic to an IC such that the circuit produces the correct output only when the key inputs are set to specific values. The correct values of the key inputs are kept secret from the untrusted foundry and programmed after manufacturing and before distribution, rendering piracy, counterfeiting and malicious design changes infeasible. The security of logic locking relies on the assumption that the untrusted foundry cannot infer the correct values of the key inputs by analysis of the circuit. This paper proposes Functional Analysis attacks on Logic Locking algorithms (abbreviated as FALL attacks). FALL attacks have two stages. Their first stage is dependent on the locking algorithm and involves analyzing structural and functional properties of locked circuits to identify a list of potential locking keys. The second stage is algorithm agnostic and introduces a powerful addition to SAT-based attacks called key confirmation. Key confirmation can identify the correct key from a list of alternatives and works even on circuits that are resilient to the SAT attack. In comparison to past work, the FALL attack is more practical as it can often succeed (90% of successful attempts in our experiments) by only analyzing the locked netlist, without requiring oracle access to an unlocked circuit. Our experimental evaluation shows that FALL attacks are able to defeat 65 out of 80 (81%) circuits locked using Stripped-Functionality Logic Locking (SFLL-HD).
An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem.
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Venue: arXiv cs.LG 2020
Year: 2020

Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value. More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying $\varepsilon$-local differential privacy will satisfy $(O(\varepsilon \sqrt{\log(1/δ)/n}), δ)$-central differential privacy. By this, we explain how the high noise and $\sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised $\varepsilon$ would indicate---at least if reports are anonymized.
Model-blind Video Denoising Via Frame-to-frame Training
Venue: arXiv cs.CV 2020
Year: 2020

Modeling the processing chain that has produced a video is a difficult reverse engineering task, even when the camera is available. This makes model based video processing a still more complex task. In this paper we propose a fully blind video denoising method, with two versions off-line and on-line. This is achieved by fine-tuning a pre-trained AWGN denoising network to the video with a novel frame-to-frame training strategy. Our denoiser can be used without knowledge of the origin of the video or burst and the post processing steps applied from the camera sensor. The on-line process only requires a couple of frames before achieving visually-pleasing results for a wide range of perturbations. It nonetheless reaches state of the art performance for standard Gaussian noise, and can be used off-line with still better performance.