OpenRaiser/Intern-Atlas huggingface dataset:
Superimposition of eye fundus images for longitudinal analysis from large public health databases
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, a method is presented for superimposition (i.e. registration) of eye fundus images from persons with diabetes screened over many years for diabetic retinopathy. The method is fully automatic and robust to camera changes and colour variations across the images both in space and time. All the stages of the process are designed for longitudinal analysis of cohort public health databases where retinal examinations are made at approximately yearly intervals. The method relies on a model correcting two radial distortions and an affine transformation between pairs of images which is robustly fitted on salient points. Each stage involves linear estimators followed by non-linear optimisation. The model of image warping is also invertible for fast computation. The method has been validated (1) on a simulated montage and (2) on public health databases with 69 patients with high quality images (271 pairs acquired mostly with different types of camera and 268 pairs acquired mostly with the same type of camera) with success rates of 92% and 98%, and five patients (20 pairs) with low quality images with a success rate of 100%. Compared to two state-of-the-art methods, ours gives better results.
Optimal Auction Design for Flexible Consumers
Venue: arXiv cs.GT 2018
Year: 2018

We study the problem of designing revenue-maximizing auctions for allocating multiple goods to flexible consumers. In our model, each consumer is interested in a subset of goods known as its flexibility set and wants to consume one good from this set. A consumer's flexibility set and its utility from consuming a good from its flexibility set are its private information. We focus on the case of nested flexibility sets --- each consumer's flexibility set can be one of $k$ nested sets. We provide several examples where such nested flexibility sets may arise. We characterize the allocation rule for an incentive compatible, individually rational and revenue-maximizing auction as the solution to an integer program. The corresponding payment rule is described by an integral equation. We then leverage the nestedness of flexibility sets to simplify the optimal auction and provide a complete characterization of allocations and payments in terms of simple thresholds.
Design Patterns in Beeping Algorithms: Examples, Emulation, and Analysis
Venue: arXiv cs.DC 2018
Year: 2018

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn (2010), processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. We refer to this model as $BL$ (beep or listen). Stronger models exist where the nodes can detect collision while they are beeping ($B_{cd}L$), listening ($BL_{cd}$), or both ($B_{cd}L_{cd}$). Beeping models are weak in essence and even simple tasks are difficult or unfeasible within. We present a set of generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: the fact of dividing the main loop into a number of specialised slots; exclusive beeps: having a single node beep at a time in a neighbourhood (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening). Based on these patterns, we provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in $BL$). The patterns make it possible to formulate these algorithms in a rather concise and elegant way. Their analyses are more technical; one of them improves significantly upon that of the best known MIS algorithm by Jeavons et al. (2016). Finally, inspired by a technique from Afek et al. (2013), our last contribution is to show that any Las Vegas algorithm relying on collision detection can be transposed into a Monte Carlo algorithm without collision detection at the cost of a logarithmic slowdown, which we prove is optimal.
Distributed Event Localization via Alternating Direction Method of Multipliers
Venue: arXiv cs.DC 2018
Year: 2018

This paper addresses the problem of distributed event localization using noisy range measurements with respect to sensors with known positions. Event localization is fundamental in many wireless sensor network applications such as homeland security, law enforcement, and environmental studies. However, most existing distributed algorithms require the target event to be within the convex hull of the deployed sensors. Based on the alternating direction method of multipliers (ADMM), we propose two scalable distributed algorithms named GS-ADMM and J-ADMM which do not require the target event to be within the convex hull of the deployed sensors. More specifically, the two algorithms can be implemented in a scenario in which the entire sensor network is divided into several clusters with cluster heads collecting measurements within each cluster and exchanging intermediate computation information to achieve localization consistency (consensus) across all clusters. This scenario is important in many applications such as homeland security and law enforcement. Simulation results confirm effectiveness of the proposed algorithms.
The complexity of tropical graph homomorphisms
Venue: arXiv cs.DS 2018
Year: 2018

A tropical graph $(H,c)$ consists of a graph $H$ and a (not necessarily proper) vertex-colouring $c$ of $H$. Given two tropical graphs $(G,c_1)$ and $(H,c)$, a homomorphism of $(G,c_1)$ to $(H,c)$ is a standard graph homomorphism of $G$ to $H$ that also preserves the vertex-colours. We initiate the study of the computational complexity of tropical graph homomorphism problems. We consider two settings. First, when the tropical graph $(H,c)$ is fixed; this is a problem called $(H,c)$-COLOURING. Second, when the colouring of $H$ is part of the input; the associated decision problem is called $H$-TROPICAL-COLOURING. Each $(H,c)$-COLOURING problem is a constraint satisfaction problem (CSP), and we show that a complexity dichotomy for the class of $(H,c)$-COLOURING problems holds if and only if the Feder-Vardi Dichotomy Conjecture for CSPs is true. This implies that $(H,c)$-COLOURING problems form a rich class of decision problems. On the other hand, we were successful in classifying the complexity of at least certain classes of $H$-TROPICAL-COLOURING problems.
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
Venue: arXiv cs.CC 2018
Year: 2018

The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute feasibility of BL-datum, the optimal BL-constant and a weak separation oracle for the BL-polytope. The same result holds for the so-called Reverse BL inequalities of Barthe. The best known algorithms for any of these tasks required at least exponential time. The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors have provided a polynomial time algorithm. This reduction implies algorithmic versions of many of the known structural results, and in some cases provide proofs that are different or simpler than existing ones. Of particular interest is the fact that the operator scaling algorithm is continuous in its input. Thus as a simple corollary of our reduction we obtain explicit bounds on the magnitude and continuity of the BL-constant in terms of the BL-data. To the best of our knowledge no such bounds were known, as past arguments relied on compactness. The continuity of BL-constants is important for developing non-linear BL inequalities that have recently found so many applications.
Decentralized Bayesian learning in dynamic games: A framework for studying informational cascades
Venue: arXiv cs.GT 2018
Year: 2018

We study the problem of Bayesian learning in a dynamical system involving strategic agents with asymmetric information. In a series of seminal papers in the literature, this problem has been investigated under a simplifying model where myopically selfish players appear sequentially and act once in the game, based on private noisy observations of the system state and public observation of past players' actions. It has been shown that there exist information cascades where users discard their private information and mimic the action of their predecessor. In this paper, we provide a framework for studying Bayesian learning dynamics in a more general setting than the one described above. In particular, our model incorporates cases where players are non-myopic and strategically participate for the whole duration of the game, and cases where an endogenous process selects which subset of players will act at each time instance. The proposed framework hinges on a sequential decomposition methodology for finding structured perfect Bayesian equilibria (PBE) of a general class of dynamic games with asymmetric information, where user-specific states evolve as conditionally independent Markov processes and users make independent noisy observations of their states. Using this methodology, we study a specific dynamic learning model where players make decisions about public investment based on their estimates of everyone's types. We characterize a set of informational cascades for this problem where learning stops for the team as a whole. We show that in such cascades, all players' estimates of other players' types freeze even though each individual player asymptotically learns its own true type.
A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
Venue: arXiv cs.DC 2018
Year: 2018

This paper presents a randomized Las Vegas distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{n})$ time and exchanges $\tilde{O}(m)$ messages (both with high probability), where $n$ is the number of nodes of the network, $D$ is the diameter, and $m$ is the number of edges. This is the first distributed MST algorithm that matches \emph{simultaneously} the time lower bound of $\tildeΩ(D + \sqrt{n})$ [Elkin, SIAM J. Comput. 2006] and the message lower bound of $Ω(m)$ [Kutten et al., J.ACM 2015] (which both apply to randomized algorithms). The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound {\em does not} work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires \emph{both} $\tildeΩ(D + \sqrt{n})$ rounds and $Ω(m)$ messages.
Multiple scan data association by convex variational inference
Venue: arXiv cs.AI 2018
Year: 2018

Data association, the reasoning over correspondence between targets and measurements, is a problem of fundamental importance in target tracking. Recently, belief propagation (BP) has emerged as a promising method for estimating the marginal probabilities of measurement to target association, providing fast, accurate estimates. The excellent performance of BP in the particular formulation used may be attributed to the convexity of the underlying free energy which it implicitly optimises. This paper studies multiple scan data association problems, i.e., problems that reason over correspondence between targets and several sets of measurements, which may correspond to different sensors or different time steps. We find that the multiple scan extension of the single scan BP formulation is non-convex and demonstrate the undesirable behaviour that can result. A convex free energy is constructed using the recently proposed fractional free energy (FFE). A convergent, BP-like algorithm is provided for the single scan FFE, and employed in optimising the multiple scan free energy using primal-dual coordinate ascent. Finally, based on a variational interpretation of joint probabilistic data association (JPDA), we develop a sequential variant of the algorithm that is similar to JPDA, but retains consistency constraints from prior scans. The performance of the proposed methods is demonstrated on a bearings only target localisation problem.
Cseq2seq: Cyclic Sequence-to-Sequence Learning
Venue: arXiv cs.CL 2018
Year: 2018

The vanilla sequence-to-sequence learning (seq2seq) reads and encodes a source sequence into a fixed-length vector only once, suffering from its insufficiency in modeling structural correspondence between the source and target sequence. Instead of handling this insufficiency with a linearly weighted attention mechanism, in this paper, we propose to use a recurrent neural network (RNN) as an alternative (Cseq2seq-I). During decoding, Cseq2seq-I cyclically feeds the previous decoding state back to the encoder as the initial state of the RNN, and reencodes source representations to produce context vectors. We surprisingly find that the introduced RNN succeeds in dynamically detecting translationrelated source tokens according to the partial target sequence. Based on this finding, we further hypothesize that the partial target sequence can act as a feedback to improve the understanding of the source sequence. To test this hypothesis, we propose cyclic sequence-to-sequence learning (Cseq2seq-II) which differs from the seq2seq only in the reintroduction of previous decoding state into the same encoder. We further perform parameter sharing on Cseq2seq-II to reduce parameter redundancy and enhance regularization. In particular, we share the weights of the encoder and decoder, and two targetside word embeddings, making Cseq2seq-II equivalent to a single conditional RNN model, with 31% parameters pruned but even better performance. Cseq2seq-II not only preserves the simplicity of seq2seq but also yields comparable and promising results on machine translation tasks. Experiments on Chinese- English and English-German translation show that Cseq2seq achieves significant and consistent improvements over seq2seq and is as competitive as the attention-based seq2seq model.
Model-based STFT phase recovery for audio source separation
Venue: arXiv cs.SD 2018
Year: 2018

For audio source separation applications, it is common to estimate the magnitude of the short-time Fourier transform (STFT) of each source. In order to further synthesizing time-domain signals, it is necessary to recover the phase of the corresponding complex-valued STFT. Most authors in this field choose a Wiener-like filtering approach which boils down to using the phase of the original mixture. In this paper, a different standpoint is adopted. Many music events are partially composed of slowly varying sinusoids and the STFT phase increment over time of those frequency components takes a specific form. This allows phase recovery by an unwrapping technique once a short-term frequency estimate has been obtained. Herein, a novel iterative source separation procedure is proposed which builds upon these results. It consists in minimizing the mixing error by means of the auxiliary function method. This procedure is initialized by exploiting the unwrapping technique in order to generate estimates that benefit from a temporal continuity property. Experiments conducted on realistic music pieces show that, given accurate magnitude estimates, this procedure outperforms the state-of-the-art consistent Wiener filter.
Uplink-Downlink Duality for Integer-Forcing
Venue: arXiv cs.IT 2018
Year: 2018

Consider a Gaussian multiple-input multiple-output (MIMO) multiple-access channel (MAC) with channel matrix $\mathbf{H}$ and a Gaussian MIMO broadcast channel (BC) with channel matrix $\mathbf{H}^{\mathsf{T}}$. For the MIMO MAC, the integer-forcing architecture consists of first decoding integer-linear combinations of the transmitted codewords, which are then solved for the original messages. For the MIMO BC, the integer-forcing architecture consists of pre-inverting the integer-linear combinations at the transmitter so that each receiver can obtain its desired codeword by decoding an integer-linear combination. In both cases, integer-forcing offers higher achievable rates than zero-forcing while maintaining a similar implementation complexity. This paper establishes an uplink-downlink duality relationship for integer-forcing, i.e., any sum rate that is achievable via integer-forcing on the MIMO MAC can be achieved via integer-forcing on the MIMO BC with the same sum power and vice versa. Using this duality relationship, it is shown that integer-forcing can operate within a constant gap of the MIMO BC sum capacity. Finally, the paper proposes a duality-based iterative algorithm for the non-convex problem of selecting optimal beamforming and equalization vectors, and establishes that it converges to a local optimum.
On the Distinguishing Number of Cyclic Tournaments: Towards the Albertson-Collins Conjecture
Venue: arXiv cs.DM 2018
Year: 2018

A distinguishing $r$-labeling of a digraph $G$ is a mapping $λ$ from the set of verticesof $G$ to the set of labels $\{1,\dots,r\}$ such that no nontrivial automorphism of $G$ preserves all the labels.The distinguishing number $D(G)$ of $G$ is then the smallest $r$ for which $G$ admits a distinguishing $r$-labeling.From a result of Gluck (David Gluck, Trivial set-stabilizers in finite permutation groups,{\em Can. J. Math.} 35(1) (1983), 59--67),it follows that $D(T)=2$ for every cyclic tournament~$T$ of (odd) order $2q+1\ge 3$.Let $V(T)=\{0,\dots,2q\}$ for every such tournament.Albertson and Collins conjectured in 1999that the canonical 2-labeling $λ^*$ given by$λ^*(i)=1$ if and only if $i\le q$ is distinguishing.We prove that whenever one of the subtournaments of $T$ induced by vertices $\{0,\dots,q\}$or $\{q+1,\dots,2q\}$ is rigid, $T$ satisfies Albertson-Collins Conjecture.Using this property, we prove that several classes of cyclic tournaments satisfy Albertson-Collins Conjecture.Moreover, we also prove that every Paley tournament satisfies Albertson-Collins Conjecture.
Modified Relay Selection and Circuit Selection for Faster Tor
Venue: arXiv cs.CR 2018
Year: 2018

Users of the Tor anonymity system suffer from lessthan- ideal performance, in part because circuit building and selection processes are not tuned for speed. In this paper, we examine both the process of selecting among pre-built circuits and the process of selecting the path of relays for use in building new circuits to improve performance while maintaining anonymity. First, we show that having three pre-built circuits available allows the Tor client to identify fast circuits and improves median time to first byte (TTFB) by 15% over congestion-aware routing, the current state-of-the-art method. Second, we propose a new path selection algorithm that includes broad geographic location information together with bandwidth to reduce delays. In Shadow simulations, we find 20% faster median TTFB and 11% faster median total download times over congestion-aware routing for accessing webpage-sized objects. Our security evaluations show that this approach leads to better or equal security against a generic relay-level adversary compared to Tor, but increased vulnerability to targeted attacks. We explore this trade-off and find settings of our system that offer good performance, modestly better security against a generic adversary, and only slightly more vulnerability to a targeted adversary.
Precise Condition Synthesis for Program Repair
Venue: arXiv cs.SE 2018
Year: 2018

Due to the difficulty of repairing defect, many research efforts have been devoted into automatic defect repair. Given a buggy program that fails some test cases, a typical automatic repair technique tries to modify the program to make all tests pass. However, since the test suites in real world projects are usually insufficient, aiming at passing the test suites often leads to incorrect patches. In this paper we aim to produce precise patches, that is, any patch we produce has a relatively high probability to be correct. More concretely, we focus on condition synthesis, which was shown to be able to repair more than half of the defects in existing approaches. Our key insight is threefold. First, it is important to know what variables in a local context should be used in an "if" condition, and we propose a sorting method based on the dependency relations between variables. Second, we observe that the API document can be used to guide the repair process, and propose document analysis technique to further filter the variables. Third, it is important to know what predicates should be performed on the set of variables, and we propose to mine a set of frequently used predicates in similar contexts from existing projects. We develop a novel program repair system, ACS, that could generate precise conditions at faulty locations. Furthermore, given the generated conditions are very precise, we can perform a repair operation that is previously deemed to be too overfitting: directly returning the test oracle to repair the defect. Using our approach, we successfully repaired 17 defects on four projects of Defects4J, which is the largest number of fully automatically repaired defects reported on the dataset so far. More importantly, the precision of our approach in the evaluation is 73.9%, which is significantly higher than previous approaches, which are usually less than 40%.
From Deterministic ODEs to Dynamic Structural Causal Models
Venue: arXiv cs.AI 2018
Year: 2018

Structural Causal Models are widely used in causal modelling, but how they relate to other modelling tools is poorly understood. In this paper we provide a novel perspective on the relationship between Ordinary Differential Equations and Structural Causal Models. We show how, under certain conditions, the asymptotic behaviour of an Ordinary Differential Equation under non-constant interventions can be modelled using Dynamic Structural Causal Models. In contrast to earlier work, we study not only the effect of interventions on equilibrium states; rather, we model asymptotic behaviour that is dynamic under interventions that vary in time, and include as a special case the study of static equilibria.
Empirical and Strong Coordination via Soft Covering with Polar Codes
Venue: arXiv cs.IT 2018
Year: 2018

We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality.