Peter Robinson - Nanyang Technological University

Peter Robinson
Are you Peter Robinson?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Peter Robinson
Affiliation
Nanyang Technological University
City
Singapore
Country
Singapore

Pubs By Year

External Links

Pub Categories

 
Computer Science - Distributed; Parallel; and Cluster Computing (15)
 
Computer Science - Data Structures and Algorithms (11)
 
Computer Science - Computer Vision and Pattern Recognition (5)
 
Statistics - Theory (4)
 
Mathematics - Statistics (4)
 
High Energy Astrophysical Phenomena (1)
 
Computer Science - Computers and Society (1)
 
Computer Science - Programming Languages (1)
 
Computer Science - Human-Computer Interaction (1)
 
Physics - Strongly Correlated Electrons (1)
 
Quantitative Biology - Quantitative Methods (1)
 
Physics - Physics and Society (1)
 
Computer Science - Information Retrieval (1)
 
Statistics - Methodology (1)

Publications Authored By Peter Robinson

Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e. Read More

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{\Omega}(D + \sqrt{n})$ [Elkin, SIAM J. Read More

Motivated by the need to understand the algorithmic foundations of distributed large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly perform computations on graphs with $n$ nodes (typically, $n \gg k$). We present (almost) tight bounds for the round complexity of two fundamental graph problems, namely triangle enumeration and PageRank computation. Our tight lower bounds, a main contribution of the paper, are established through an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines for solving a problem. Read More

Central limit theorems are established for the sum, over a spatial region, of observations from a linear process on a $d$-dimensional lattice. This region need not be rectangular, but can be irregularly-shaped. Separate results are established for the cases of positive strong dependence, short range dependence, and negative dependence. Read More

2016Jan
Authors: Yuxiang Jiang, Tal Ronnen Oron, Wyatt T Clark, Asma R Bankapur, Daniel D'Andrea, Rosalba Lepore, Christopher S Funk, Indika Kahanda, Karin M Verspoor, Asa Ben-Hur, Emily Koo, Duncan Penfold-Brown, Dennis Shasha, Noah Youngs, Richard Bonneau, Alexandra Lin, Sayed ME Sahraeian, Pier Luigi Martelli, Giuseppe Profiti, Rita Casadio, Renzhi Cao, Zhaolong Zhong, Jianlin Cheng, Adrian Altenhoff, Nives Skunca, Christophe Dessimoz, Tunca Dogan, Kai Hakala, Suwisa Kaewphan, Farrokh Mehryary, Tapio Salakoski, Filip Ginter, Hai Fang, Ben Smithers, Matt Oates, Julian Gough, Petri Törönen, Patrik Koskinen, Liisa Holm, Ching-Tai Chen, Wen-Lian Hsu, Kevin Bryson, Domenico Cozzetto, Federico Minneci, David T Jones, Samuel Chapman, Dukka B K. C., Ishita K Khan, Daisuke Kihara, Dan Ofer, Nadav Rappoport, Amos Stern, Elena Cibrian-Uhalte, Paul Denny, Rebecca E Foulger, Reija Hieta, Duncan Legge, Ruth C Lovering, Michele Magrane, Anna N Melidoni, Prudence Mutowo-Meullenet, Klemens Pichler, Aleksandra Shypitsyna, Biao Li, Pooya Zakeri, Sarah ElShal, Léon-Charles Tranchevent, Sayoni Das, Natalie L Dawson, David Lee, Jonathan G Lees, Ian Sillitoe, Prajwal Bhat, Tamás Nepusz, Alfonso E Romero, Rajkumar Sasidharan, Haixuan Yang, Alberto Paccanaro, Jesse Gillis, Adriana E Sedeño-Cortés, Paul Pavlidis, Shou Feng, Juan M Cejuela, Tatyana Goldberg, Tobias Hamp, Lothar Richter, Asaf Salamov, Toni Gabaldon, Marina Marcet-Houben, Fran Supek, Qingtian Gong, Wei Ning, Yuanpeng Zhou, Weidong Tian, Marco Falda, Paolo Fontana, Enrico Lavezzo, Stefano Toppo, Carlo Ferrari, Manuel Giollo, Damiano Piovesan, Silvio Tosatto, Angela del Pozo, José M Fernández, Paolo Maietta, Alfonso Valencia, Michael L Tress, Alfredo Benso, Stefano Di Carlo, Gianfranco Politano, Alessandro Savino, Hafeez Ur Rehman, Matteo Re, Marco Mesiti, Giorgio Valentini, Joachim W Bargsten, Aalt DJ van Dijk, Branislava Gemovic, Sanja Glisic, Vladmir Perovic, Veljko Veljkovic, Nevena Veljkovic, Danillo C Almeida-e-Silva, Ricardo ZN Vencio, Malvika Sharan, Jörg Vogel, Lakesh Kansakar, Shanshan Zhang, Slobodan Vucetic, Zheng Wang, Michael JE Sternberg, Mark N Wass, Rachael P Huntley, Maria J Martin, Claire O'Donovan, Peter N Robinson, Yves Moreau, Anna Tramontano, Patricia C Babbitt, Steven E Brenner, Michal Linial, Christine A Orengo, Burkhard Rost, Casey S Greene, Sean D Mooney, Iddo Friedberg, Predrag Radivojac

Background: The increasing volume and variety of genotypic and phenotypic data is a major defining characteristic of modern biomedical sciences. At the same time, the limitations in technology for generating data and the inherently stochastic nature of biomolecular events have led to the discrepancy between the volume of data and the amount of knowledge gleaned from it. A major bottleneck in our ability to understand the molecular underpinnings of life is the assignment of function to biological macromolecules, especially proteins. Read More

The problem of face alignment has been intensively studied in the past years. A large number of novel methods have been proposed and reported very good performance on benchmark dataset such as 300W. However, the differences in the experimental setting and evaluation metric, missing details in the description of the methods make it hard to reproduce the results reported and evaluate the relative merits. Read More

We report the temperature $T$ and magnetic field $H$ dependence of the thermopower $S$ of an itinerant triangular antiferromagnet PdCrO$_2$ in high magnetic fields up to 32 T. In the paramagnetic phase, the zero-field thermopower is positive with a value typical of good metals with a high carrier density. In marked contrast to typical metals, however, $S$ decreases rapidly with increasing magnetic field, approaching zero at the maximum field scale for $T >$ 70 K. Read More

Rotation dynamics of eigenvectors of modular network adjacency matrices under random perturbations are presented. In the presence of $q$ communities, the number of eigenvectors corresponding to the $q$ largest eigenvalues form a "community" eigenspace and rotate together, but separately from that of the "bulk" eigenspace spanned by all the other eigenvectors. Using this property, the number of modules or clusters in a network can be estimated in an algorithm-independent way. Read More

In this paper we present a method for localisation of facial landmarks on human and sheep. We introduce a new feature extraction scheme called triplet-interpolated feature used at each iteration of the cascaded shape regression framework. It is able to extract features from similar semantic location given an estimated shape, even when head pose variations are large and the facial landmarks are very sparsely distributed. Read More

In this paper we propose a supervised initialization scheme for cascaded face alignment based on explicit head pose estimation. We first investigate the failure cases of most state of the art face alignment approaches and observe that these failures often share one common global property, i.e. Read More

Images of the eye are key in several computer vision problems, such as shape registration and gaze estimation. Recent large-scale supervised methods for these problems require time-consuming data collection and manual annotation, which can be unreliable. We propose synthesizing perfectly labelled photo-realistic training data in a fraction of the time. Read More

We propose a new and easy-to-use method for identifying cointegrated components of nonstationary time series, consisting of an eigenalysis for a certain non-negative definite matrix. Our setting is model-free, and we allow the integer-valued integration orders of the observable series to be unknown, and to possibly differ. Consistency of estimates of the cointegration space and cointegration rank is established both when the dimension of the observable time series is fixed as sample size increases, and when it diverges slowly. Read More

Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly perform computations on graphs with $n$ nodes (typically, $n \gg k$). The input graph is assumed to be initially randomly partitioned among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Read More

We study distributed agreement in synchronous directed dynamic networks, where an omniscient message adversary controls the availability of communication links. We prove that consensus is impossible under a message adversary that guarantees weak connectivity only, and introduce vertex-stable root components (VSRCs) as a means for circumventing this impossibility: A VSRC(k, d) message adversary guarantees that, eventually, there is an interval of $d$ consecutive rounds where every communication graph contains at most $k$ strongly (dynamic) connected components consisting of the same processes, which have at most outgoing links to the remaining processes. We present a consensus algorithm that works correctly under a VSRC(1, 4H + 2) message adversary, where $H$ is the dynamic causal network diameter. Read More

Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e. Read More

Individuals with Autism Spectrum Conditions (ASC) have marked difficulties using verbal and non-verbal communication for social interaction. The running ASC-Inclusion project aims to help children with ASC by allowing them to learn how emotions can be expressed and recognised via playing games in a virtual world. The platform includes analysis of users' gestures, facial, and vocal expressions using standard microphone and web-cam or a depth sensor, training through games, text communication with peers, animation, video and audio clips. Read More

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a message-passing distributed computing model for graph processing and present lower bounds and algorithms for several graph problems. This work is inspired by recent large-scale graph processing systems (e.g. Read More

2013Oct
Affiliations: 1Indian Institute of Technology Madras, 2Indian Institute of Technology Madras, 3Indian Institute of Technology Madras, 4Nanyang Technological University

We consider the problem of electing a leader among nodes in a highly dynamic network where the adversary has unbounded capacity to insert and remove nodes (including the leader) from the network and change connectivity at will. We present a randomized Las Vegas algorithm that (re)elects a leader in O(D\log n) rounds with high probability, where D is a bound on the dynamic diameter of the network and n is the maximum number of nodes in the network at any point in time. We assume a model of broadcast-based communication where a node can send only 1 message of O(\log n) bits per round and is not aware of the receivers in advance. Read More

We study robust and efficient distributed algorithms for searching, storing, and maintaining data in dynamic Peer-to-Peer (P2P) networks. P2P networks are highly dynamic networks that experience heavy node churn (i.e. Read More

This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$-node networks that runs in O(1) rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. Read More

We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders --- whose expansion properties hold {\em deterministically} --- that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only {\em probabilistic} guarantees on the network expansion which {\em rapidly degrade} in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under {\em adversarial} insertions and deletions. Read More

Power law or generalized polynomial regressions with unknown real-valued exponents and coefficients, and weakly dependent errors, are considered for observations over time, space or space--time. Consistency and asymptotic normality of nonlinear least-squares estimates of the parameters are established. The joint limit distribution is singular, but can be used as a basis for inference on either exponents or coefficients. Read More

We study distributed computation in synchronous dynamic networks where an omniscient adversary controls the unidirectional communication links. Its behavior is modeled as a sequence of directed graphs representing the active (i.e. Read More

We consider the estimation of parametric fractional time series models in which not only is the memory parameter unknown, but one may not know whether it lies in the stationary/invertible region or the nonstationary or noninvertible regions. In these circumstances, a proof of consistency (which is a prerequisite for proving asymptotic normality) can be difficult owing to nonuniform convergence of the objective function over a large admissible parameter space. In particular, this is the case for the conditional sum of squares estimate, which can be expected to be asymptotically efficient under Gaussianity. Read More

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node {\em churn}. Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Read More

Despite of being quite similar agreement problems, consensus and general k-set agreement require surprisingly different techniques for proving the impossibility in asynchronous systems with crash failures: Rather than relatively simple bivalence arguments as in the impossibility proof for consensus (= 1-set agreement) in the presence of a single crash failure, known proofs for the impossibility of k-set agreement in systems with at least k>1 crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of k-set agreement in various message passing settings, which is based on a simple reduction to the consensus impossibility in a certain subsystem. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of k-set agreement in several message-passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and (iii) asynchronous systems augmented with failure detectors. Read More

In this paper we consider the k-set agreement problem in distributed message-passing systems using a round-based approach: Both synchrony of communication and failures are captured just by means of the messages that arrive within a round, resulting in round-by-round communication graphs that can be characterized by simple communication predicates. We introduce the weak communication predicate PSources(k) and show that it is tight for k-set agreement, in the following sense: We (i) prove that there is no algorithm for solving (k-1)-set agreement in systems characterized by PSources(k), and (ii) present a novel distributed algorithm that achieves k-set agreement in runs where PSources(k) holds. Our algorithm uses local approximations of the stable skeleton graph, which reflects the underlying perpetual synchrony of a run. Read More

The properties of a massive star prior to its final explosion are imprinted in the circumstellar medium (CSM) created by its wind and termination shock. We perform a detailed, comprehensive calculation of the time-variable and angle-dependent transmission spectra of an average-luminosity Gamma-Ray Burst (GRB) which explodes in the CSM structure produced by the collapse of a 20 Msun, rapidly rotating, Z=0.001 progenitor star. Read More

Strong consistency and asymptotic normality of the Gaussian pseudo-maximum likelihood estimate of the parameters in a wide class of ARCH$(\infty)$ processes are established. The conditions are shown to hold in case of exponential and hyperbolic decay in the ARCH weights, though in the latter case a faster decay rate is required for the central limit theorem than for the law of large numbers. Particular parameterizations are discussed. Read More

This paper presents the multi-threading and internet message communication capabilities of Qu-Prolog. Message addresses are symbolic and the communications package provides high-level support that completely hides details of IP addresses and port numbers as well as the underlying TCP/IP transport layer. The combination of the multi-threads and the high level inter-thread message communications provide simple, powerful support for implementing internet distributed intelligent applications. Read More