Search Constraints
Number of results to display per page
Search Results

 Resource Type:
 Article
 Creator:
 Albert, Jacques, Dakka, Milad A., Shevchenko, Yanina, and Chen, Chengkun
 Abstract:
 We show that the tiltedgratingassisted excitation of surface plasmon polaritons on gold coated singlemode optical fibers depends strongly on the state of polarization of the coreguided light, even in fibers with cylindrical symmetry. Rotating the linear polarization of the guided light by 90° relative to the grating tilt plane is sufficient to turn the plasmon resonances on and off with more than 17 dB of extinction ratio. By monitoring the amplitude changes of selected individual cladding mode resonances we identify what we believe to be a new refractive index measurement method that is shown to be accurate to better than 5 × 105.
 Date Created:
 20100301

 Resource Type:
 Article
 Creator:
 Lever, Rosemary, Ouellette, Gene, Pagan, Stephanie, and Sénéchal, Monique
 Abstract:
 The goal of the present intervention research was to test whether guided invented spelling would facilitate entry into reading for atrisk kindergarten children. The 56 participating children had poor phoneme awareness, and as such, were at risk of having difficulty acquiring reading skills. Children were randomly assigned to one of three training conditions: invented spelling, phoneme segmentation, or storybook reading. All children participated in 16 small group sessions over eight weeks. In addition, children in the three training conditions received letterknowledge training and worked on the same 40 stimulus words that were created from an array of 14 letters. The findings were clear: on pretest, there were no differences between the three conditions on measures of early literacy and vocabulary, but, after training, invented spelling children learned to read more words than did the other children. As expected, the phonemesegmentation and inventedspelling children were better on phoneme awareness than were the storybookreading children. Most interesting, however, both the invented spelling and the phonemesegmentation children performed similarly on phoneme awareness suggesting that the differential effect on learning to read was not due to phoneme awareness per se. As such, the findings support the view that invented spelling is an exploratory process that involves the integration of phoneme and orthographic representations. With guidance and developmentally appropriate feedback, invented spelling provides a milieu for children to explore the relation between oral language and written symbols that can facilitate their entry in reading.
 Date Created:
 20120401

 Resource Type:
 Article
 Creator:
 Shao, LiYang, Albert, Jacques, Coyle, Jason P., and Barry, Seán T.
 Abstract:
 The conformal coating of a 50 nmthick layer of copper nanoparticles deposited with pulse chemical vapor deposition of a copper (I) guanidinate precursor on the cladding of a single mode optical fiber was monitored by using a tilted fiber Bragg grating (TFBG) photoinscribed in the fiber core. The pulseperpulse growth of the copper nanoparticles is readily obtained from the position and amplitudes of resonances in the reflection spectrum of the grating. In particular, we confirm that the real part of the effective complex permittivity of the deposited nanostructured copper layer is an order of magnitude larger than that of a bulk copper film at an optical wavelength of 1550 nm. We further observe a transition in the growth behavior from granular to continuous film (as determined from the complex material permittivity) after approximately 20 pulses (corresponding to an effective thickness of 25 nm). Finally, despite the remaining granularity of the film, the final coppercoated optical fiber is shown to support plasmon waves suitable for sensing, even after the growth of a thin oxide layer on the copper surface.
 Date Created:
 20110601

 Resource Type:
 Article
 Creator:
 Hayes, M. John, Langlois, Robert, and Weiss, Abraham
 Abstract:
 Conventional training simulators commonly use a hexapod configuration to provide motion cues. While widely used, studies have shown that hexapods are incapable of producing the range of motion required to achieve high fidelity simulation required in many applications. A novel alternative is the Atlas motion platform. This paper presents a new generalized kinematic model of the platform which can be applied to any spherical platform actuated by three omnidirectional wheels. In addition, conditions for slipfree and singularityfree motions are identified. Two illustrative examples are given for different omnidirectional wheel configurations.
 Date Created:
 20110201

 Resource Type:
 Article
 Creator:
 Adler, Andy, Loyka, Sergey, and Youmaran, Richard
 Date Created:
 20090101

 Resource Type:
 Article
 Creator:
 Morin, Pat, Hurtado, Ferran, Bose, Prosenjit, and Carmi, Paz
 Abstract:
 We prove that, for every simple polygon P having k ≥ 1 reflex vertices, there exists a point q ε P such that every halfpolygon that contains q contains nearly 1/2(k + 1) times the area of P. We also give a family of examples showing that this result is the best possible.
 Date Created:
 20110401

 Resource Type:
 Article
 Creator:
 Wiener, Michael J. and Van Oorschot, Paul C.
 Abstract:
 A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meetinthemiddle attacks such as a knownplaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most costeffective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA1, MDC2, and MDC4; and double encryption and threekey triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a doubleDES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meetinthemiddle attack on doubleDES. Based on this attack, doubleDES offers only 17 more bits of security than singleDES.
 Date Created:
 19990101

 Resource Type:
 Article
 Creator:
 Wiener, Michael J., Van Oorschot, Paul C., and Diffie, Whitfield
 Abstract:
 We discuss twoparty mutual authentication protocols providing authenticated key exchange, focusing on those using asymmetric techniques. A simple, efficient protocol referred to as the stationtostation (STS) protocol is introduced, examined in detail, and considered in relation to existing protocols. The definition of a secure protocol is considered, and desirable characteristics of secure protocols are discussed.
 Date Created:
 19920601

 Resource Type:
 Article
 Creator:
 Yan, Donghang, Wang, Zhiyuan, Yu, Hongan, Wu, Xianguo, and Zhang, Jidong
 Abstract:
 A near infrared (NIR) electrochromic attenuator based on a dinuclear ruthenium complex and polycrystalline tungsten oxide was fabricated and characterized. The results show that the use of the NIRabsorbing ruthenium complex as a counter electrode material can improve the device performance. By replacing the visible electrochromic ferrocene with the NIRabsorbing ruthenium complex, the optical attenuation at 1550 nm was enhanced from 19.1 to 30.0 dB and color efficiency also increased from 29.2 to 121.2 cm2/C.
 Date Created:
 20051201

 Resource Type:
 Article
 Creator:
 Bose, Prosenjit, Overmars, M., Wilfong, G., Toussaint, G., GarciaLopez, J., Zhu, B., Asberg, B., and Blanco, G.
 Abstract:
 We study the feasibility of design for a layerdeposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid causes the liquid to harden. In order to understand the power as well as the limitations of this manufacturing process better, we define a mathematical model of stereolithography (referred to as vertical stereolithography) and analyze the class of objects that can be constructed under the assumptions of the model. Given an object (modeled as a polygon or a polyhedron), we give algorithms that decide in O(n) time (where n is the number of vertices in the polygon or polyhedron) whether or not the object can be constructed by vertical stereolithography. If the answer is in the affirmative, the algorithm reports a description of all the orientations in which the object can be made. We also show that the objects built with vertical stereolithography are precisely those that can be made with a 3axis NC machine. We then define a more flexible model that more accurately reflects the actual capabilities of stereolithography (referred to as variableangle stereolithography) and again study the class of feasible objects for this model. We give an O(n)time algorithm for polygons and O(n log n) as well as O(n)time algorithms for polyhedra. We show that objects formed with variableangle stereolithography can also be constructed using another manufacturing process known as gravity casting. Furthermore, we show that the polyhedral objects formed by vertical stereolithography are closely related to polyhedral terrains which are important structures in geographic information systems (GIS) and computational geometry. In fact, an object built with variableangle stereolithography resembles a terrain with overhangs, thus initiating the study of more realistic terrains than the standard ones considered in geographic information systems. Finally, we relate our results to the area of grasping in robotics by showing that the polygonal and polyhedral objects that can be built by vertical stereolithography can be clamped by parallel jaw grippers with any positivesized gripper.
 Date Created:
 19970101

 Resource Type:
 Article
 Creator:
 Sack, JörgRüdiger, Maheshwari, Anil, and Lingas, A.
 Abstract:
 We provide optimal parallel solutions to several linkdistance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P. 2. Minimum rectilinear link paths from any segment inside P to all vertices of P. 3. The rectilinear window (histogram) partition of P. 4. Both covering radii and vertex intervals for any diagonal of P. 5. A data structure to support rectilinear linkdistance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is based on a new lineartime sequential algorithm for this problem which is also provided here. This improves on the previously bestknown sequential algorithm for this problem which used O(n log n) time and space.5 We develop techniques for solving linkdistance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
 Date Created:
 19950901

 Resource Type:
 Conference Proceeding
 Creator:
 Peng, Mengfei, Shi, Wei, Croft, William Lee, and Corriveau, JeanPierre
 Abstract:
 New threats to networks are constantly arising. This justifies protecting network assets and mitigating the risk associated with attacks. In a distributed environment, researchers aim, in particular, at eliminating faulty network entities. More specifically, much research has been conducted on locating a single static black hole, which is defined as a network site whose existence is known a priori and that disposes of any incoming data without leaving any trace of this occurrence. However, the prevalence of faulty nodes requires an algorithm able to (a) identify faulty nodes that can be repaired without human intervention and (b) locate black holes, which are taken to be faulty nodes whose repair does require human intervention. In this paper, we consider a specific attack model that involves multiple faulty nodes that can be repaired by mobile software agents, as well as a virus v that can infect a previously repaired faulty node and turn it into a black hole. We refer to the task of repairing multiple faulty nodes and pointing out the location of the black hole as the Faulty Node Repair and Dynamically Spawned Black Hole Search. Wefirst analyze the attack model we put forth. We then explain (a) how to identify whether a node is either (1) a normal node or (2) a repairable faulty node or (3) the black hole that has been infected by virus v during the search/repair process and, (b) how to perform the correct relevant actions. These two steps constitute a complex task, which, we explain, significantly differs from the traditional Black Hole Search. We continue by proposing an algorithm to solve this problem in an asynchronous ring network with only one whiteboard (which resides in a node called the homebase). We prove the correctness of our solution and analyze its complexity by both theoretical analysis and experiment evaluation. We conclude that, using our proposed algorithm, b + 4 agents can repair all faulty nodes and locate the black hole infected by a virus v within finite time. Our algorithm works even when the number of faulty nodes b is unknown a priori.
 Date Created:
 20170101

 Resource Type:
 Conference Proceeding
 Creator:
 Guo, Yuhong and Li, Xin
 Abstract:
 Semantic scene classification is a challenging problem in computer vision. In this paper, we present a novel multilevel active learning approach to reduce the human annotation effort for training robust scene classification models. Different from most existing active learning methods that can only query labels for selected instances at the target categorization level, i.e., the scene class level, our approach establishes a semantic framework that predicts scene labels based on a latent objectbased semantic representation of images, and is capable to query labels at two different levels, the target scene class level (abstractive high level) and the latent object class level (semantic middle level). Specifically, we develop an adaptive active learning strategy to perform multilevel label query, which maintains the default label query at the target scene class level, but switches to the latent object class level whenever an "unexpected" target class label is returned by the labeler. We conduct experiments on two standard scene classification datasets to investigate the efficacy of the proposed approach. Our empirical results show the proposed adaptive multilevel active learning approach can outperform both baseline active learning methods and a stateoftheart multilevel active learning method.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 Oommen, B. John and Polk, Spencer
 Abstract:
 The field of game playing is a particularly wellstudied area within the context of AI, leading to the development of powerful techniques, such as the alphabeta search, capable of achieving competitive game play against an intelligent opponent. It is well known that tree pruning strategies, such as alphabeta, benefit strongly from proper move ordering, that is, searching the best element first. Inspired by the formerly unrelated field of Adaptive Data Structures (ADSs), we have previously introduced the HistoryADS technique, which employs an adaptive list to achieve effective and dynamic move ordering, in a domain independent fashion, and found that it performs well in a wide range of cases. However, previous work did not compare the performance of the HistoryADS heuristic to any established move ordering strategy. In an attempt to address this problem, we present here a comparison to two wellknown, acclaimed strategies, which operate on a similar philosophy to the HistoryADS, the History Heuristic, and the Killer Moves technique. We find that, in a wide range of twoplayer and multiplayer games, at various points in the game’s progression, the HistoryADS performs at least as well as these strategies, and, in fact, outperforms them in the majority of cases.
 Date Created:
 20160101

 Resource Type:
 Conference Proceeding
 Creator:
 Oommen, B. John and Astudillo, César A.
 Abstract:
 We present a method that employs a treebased Neural Network (NN) for performing classification. The novel mechanism, apart from incorporating the information provided by unlabeled and labeled instances, rearranges the nodes of the tree as per the laws of Adaptive Data Structures (ADSs). Particularly, we investigate the Pattern Recognition (PR) capabilities of the TreeBased TopologyOriented SOM (TTOSOM) when Conditional Rotations (CONROT) [8] are incorporated into the learning scheme. The learning methodology inherits all the properties of the TTOSOMbased classifier designed in [4]. However, we now augment it with the property that frequently accessed nodes are moved closer to the root of the tree. Our experimental results show that on average, the classification capabilities of our proposed strategy are reasonably comparable to those obtained by some of the stateoftheart classification schemes that only use labeled instances during the training phase. The experiments also show that improved levels of accuracy can be obtained by imposing trees with a larger number of nodes.
 Date Created:
 20150101

 Resource Type:
 Conference Proceeding
 Creator:
 Tavasoli, Hanane, Oommen, B. John, and Yazidi, Anis
 Abstract:
 In this paper, we propose a novel online classifier for complex data streams which are generated from nonstationary stochastic properties. Instead of using a single training model and counters to keep important data statistics, the introduced online classifier scheme provides a realtime selfadjusting learning model. The learning model utilizes the multiplicationbased update algorithm of the Stochastic Learning Weak Estimator (SLWE) at each time instant as a new labeled instance arrives. In this way, the data statistics are updated every time a new element is inserted, without requiring that we have to rebuild its model when changes occur in the data distributions. Finally, and most importantly, the model operates with the understanding that the correct classes of previouslyclassified patterns become available at a later juncture subsequent to some time instances, thus requiring us to update the training set and the training model. The results obtained from rigorous empirical analysis on multinomial distributions, is remarkable. Indeed, it demonstrates the applicability of our method on synthetic datasets, and proves the advantages of the introduced scheme.
 Date Created:
 20160101

 Resource Type:
 Conference Proceeding
 Creator:
 Yazidi, Anis, Oommen, B. John, and Hammer, Hugo Lewi
 Abstract:
 The problem of clustering, or unsupervised classification, has been solved by a myriad of techniques, all of which depend, either directly or implicitly, on the Bayesian principle of optimal classification. To be more specific, within a Bayesian paradigm, if one is to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strategy would be to achieve this based on the distance from the corresponding means or central points in the respective distributions. When this principle is applied in clustering, one would assign an unassigned sample into the cluster whose mean is the closest, and this can be done in either a bottomup or a topdown manner. This paper pioneers a clustering achieved in an “AntiBayesian” manner, and is based on the breakthrough classification paradigm pioneered by Oommen et al. The latter relies on a radically different approach for classifying data points based on the noncentral quantiles of the distributions. Surprisingly and counterintuitively, this turns out to work equally or closetoequally well to an optimal supervised Bayesian scheme, which thus begs the natural extension to the unexplored arena of clustering. Our algorithm can be seen as the AntiBayesian counterpart of the wellknown kmeans algorithm (The fundamental AntiBayesian paradigm need not just be used to the kmeans principle. Rather, we hypothesize that it can be adapted to any of the scores of techniques that is indirectly based on the Bayesian paradigm.), where we assign points to clusters using quantiles rather than the clusters’ centroids. Extensive experimentation (This paper contains the prima facie results of experiments done on one and twodimensional data. The extensions to multidimensional data are not included in the interest of space, and would use the corresponding multidimensional AntiNa¨ıveBayes classification rules given in [1].) demonstrates that our AntiBayesian clustering converges fast and with precision results competitive to a kmeans clustering.
 Date Created:
 20150101

 Resource Type:
 Conference Proceeding
 Creator:
 Polk, Spencer and Oommen, B. John
 Abstract:
 This paper pioneers the avenue of enhancing a wellknown paradigm in game playing, namely the use of Historybased heuristics, with a totallyunrelated area of computer science, the field of Adaptive Data Structures (ADSs). It is a wellknown fact that highlyregarded game playing strategies, such as alphabeta search, benefit strongly from proper move ordering, and from this perspective, the History heuristic is, probably, one of the most acclaimed techniques used to achieve AIbased game playing. Recently, the authors of this present paper have shown that techniques derived from the field of ADSs, which are concerned with query optimization in a data structure, can be applied to move ordering in multiplayer games. This was accomplished by ranking opponent threat levels. The work presented in this paper seeks to extend the utility of ADSbased techniques to twoplayer and multiplayer games, through the development of a new move ordering strategy that incorporates the historical advantages of the moves. The resultant technique, the HistoryADS heuristic, has been found to produce substantial (i.e, even up to 70%) savings in a variety of twoplayer and multiplayer games, at varying ply depths, and at both initial and midgame board states. As far as we know, results of this nature have not been reported in the literature before.
 Date Created:
 20150101

 Resource Type:
 Conference Proceeding
 Creator:
 Oommen, B. John and Kim, SangWoon
 Abstract:
 This paper deals with the relatively new field of sequencebased estimation which involves utilizing both the information in the observations and in their sequence of appearance. Our intention is to obtain Maximum Likelihood estimates by “extracting” the information contained in the observations when perceived as a sequence rather than as a set. The results of [15] introduced the concepts of Sequence Based Estimation (SBE) for the Binomial distribution. This current paper generalizes these results for the multinomial “twoatatime” scenario. We invoke a novel phenomenon called “Occlusion” that can be described as follows: By “concealing” certain observations, we map the estimation problem onto a lowerdimensional binomial space. Once these occluded SBEs have been computed, we demonstrate how the overall Multinomial SBE (MSBE) can be obtained by mapping several lowerdimensional estimates onto the original higherdimensional space. We formally prove and experimentally demonstrate the convergence of the corresponding estimates.
 Date Created:
 20160101

 Resource Type:
 Conference Proceeding
 Creator:
 Labiche, Yvan and Barros, Márcio
 Date Created:
 20150101

 Resource Type:
 Conference Proceeding
 Creator:
 Kim, SangWoon and Oommen, B. John
 Abstract:
 The Maximum Likelihood (ML) and Bayesian estimation paradigms work within the model that the data, from which the parameters are to be estimated, is treated as a set rather than as a sequence. The pioneering paper that dealt with the field of sequencebased estimation [2] involved utilizing both the information in the observations and in their sequence of appearance. The results of [2] introduced the concepts of Sequence Based Estimation (SBE) for the Binomial distribution, where the authors derived the corresponding MLE results when the samples are taken twoatatime, and then extended these for the cases when they are processed threeatatime, fouratatime etc. These results were generalized for the multinomial “twoatatime” scenario in [3]. This paper (This paper is dedicated to the memory of Dr. Mohamed Kamel, who was a close friend of the first author.) now further generalizes the results found in [3] for the multinomial case and for subsequences of length 3. The strategy used in [3] (and also here) involves a novel phenomenon called “Occlusion” that has not been reported in the field of estimation. The phenomenon can be described as follows: By occluding (hiding or concealing) certain observations, we map the estimation problem onto a lowerdimensional space, i.e., onto a binomial space. Once these occluded SBEs have been computed, the overall Multinomial SBE (MSBE) can be obtained by combining these lowerdimensional estimates. In each case, we formally prove and experimentally demonstrate the convergence of the corresponding estimates.
 Date Created:
 20160101

 Resource Type:
 Conference Proceeding
 Creator:
 Maheshwari, Anil, Nandy, Ayan, Smid, Michiel, and Das, Sandip
 Abstract:
 Consider a line segment R consisting of n facilities. Each facility is a point on R and it needs to be assigned exactly one of the colors from a given palette of c colors. At an instant of time only the facilities of one particular color are 'active' and all other facilities are 'dormant'. For the set of facilities of a particular color, we compute the one dimensional Voronoi diagram, and find the cell, i.e, a segment of maximum length. The users are assumed to be uniformly distributed over R and they travel to the nearest among the facilities of that particular color that is active. Our objective is to assign colors to the facilities in such a way that the length of the longest cell is minimized. We solve this optimization problem for various values of n and c. We propose an optimal coloring scheme for the number of facilities n being a multiple of c as well as for the general case where n is not a multiple of c. When n is a multiple of c, we compute an optimal scheme in Θ(n) time. For the general case, we propose a coloring scheme that returns the optimal in O(n2logn) time.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 Bertossi, Leopoldo
 Abstract:
 A correspondence between database tuples as causes for query answers in databases and tuplebased repairs of inconsistent databases with respect to denial constraints has already been established. In this work, answerset programs that specify repairs of databases are used as a basis for solving computational and reasoning problems about causes. Here, causes are also introduced at the attribute level by appealing to a both nullbased and attributebased repair semantics. The corresponding repair programs are presented, and they are used as a basis for computation and reasoning about attributelevel causes.
 Date Created:
 20180101

 Resource Type:
 Conference Proceeding
 Creator:
 Dujmović, Vida, De Carufel, JeanLou, Bose, Prosenjit, and Paradis, Frédérik
 Abstract:
 The wellseparated pair decomposition (WSPD) of the complete Euclidean graph defined on points in ℝ2 (Callahan and Kosaraju [JACM, 42 (1): 6790, 1995]) is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPDspanner) is a 1 + 8/(s − 4)spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive localrouting strategies exist for various spanners such as Yaographs, Θgraphs, and variants of Delaunay graphs, few localrouting strategies are known for any WSPDspanner. Our main contribution is a localrouting algorithm with a nearoptimal competitive routing ratio of 1 + O(1/s) on a WSPDspanner. Specifically, we present a 2local and a 1local routing algorithm on a WSPDspanner with competitive routing ratios of 1+6/(s−2)+4/s and 1+6/(s−2)+ 6/s + 4/(s2 − 2s) + 8/s2respectively.
 Date Created:
 20170101

 Resource Type:
 Conference Proceeding
 Creator:
 Lanthier, Mark, Velazquez, Elio, and Santoro, Nicola
 Abstract:
 This paper proposes a proactive solution to the Frugal Feeding Problem (FFP) in Wireless Sensor Networks. The FFP attempts to find energyefficient routes for a mobile service entity to rendezvous with each member of a team of mobile robots. Although the complexity of the FFP is similar to the Traveling Salesman Problem (TSP), we propose an efficient solution, completely distributed and localized for the case of a fixed rendezvous location (i.e., service facility with limited number of docking ports) and mobile capable entities (sensors). Our proactive solution reduces the FFP to finding energyefficient routes in a dynamic Compass Directed unit Graph (CDG). The proposed CDG incorporates ideas from forward progress routing and the directionality of compass routing in an energyaware unit subgraph. Navigating the CDG guarantees that each sensor will reach the rendezvous location in a finite number of steps. The ultimate goal of our solution is to achieve energy equilibrium (i.e., no further sensor losses due to energy starvation) by optimizing the use of the shared resource (recharge station). We also examine the impact of critical parameters such as transmission range, cost of mobility and sensor knowledge in the overall performance.
 Date Created:
 20111114

 Resource Type:
 Conference Proceeding
 Creator:
 Guo, Yuhong and Li, Xin
 Abstract:
 Multilabel classification is a central problem in many application domains. In this paper, we present a novel supervised bidirectional model that learns a lowdimensional midlevel representation for multilabel classification. Unlike traditional multilabel learning methods which identify intermediate representations from either the input space or the output space but not both, the midlevel representation in our model has two complementary parts that capture intrinsic information of the input data and the output labels respectively under the autoencoder principle while augmenting each other for the target output label prediction. The resulting optimization problem can be solved efficiently using an iterative procedure with alternating steps, while closedform solutions exist for one major step. Our experiments conducted on a variety of multilabel data sets demonstrate the efficacy of the proposed bidirectional representation learning model for multilabel classification.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 White, Anthony and SalehiAbari, Amirali
 Abstract:
 Autonomous agents require trust and reputation concepts in order to identify communities of agents with which to interact reliably in ways analogous to humans. Agent societies are invariably heterogeneous, with multiple decision making policies and actions governing their behaviour. Through the introduction of naive agents, this paper shows empirically that while learning agents can identify malicious agents through direct interaction, naive agents compromise utility through their inability to discern malicious agents. Moreover, the impact of the proportion of naive agents on the society is analyzed. The paper demonstrates that there is a need for witness interaction trust to detect naive agents in addition to the need for direct interaction trust to detect malicious agents. By proposing a set of policies, the paper demonstrates how learning agents can isolate themselves from naive and malicious agents.
 Date Created:
 20100720

 Resource Type:
 Conference Proceeding
 Creator:
 Prencipe, Giuseppe, Cáceres, Edson, Chan, Albert, and Dehne, Frank
 Abstract:
 In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and the bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. Our algorithms require O(log p) and O(log2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N/p local memory per processor, N=G. The algorithms assume that N/ p ≥ p€ for some fixed€ > 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log2 p) supersteps, respectively, O(g log(p) N p) communication time, and O(log(p) N p) local computation time. Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutiveones property for (0, 1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.
 Date Created:
 20000101

 Resource Type:
 Conference Proceeding
 Creator:
 Maheshwari, Anil and Zeh, Norbert
 Abstract:
 We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadthfirst search (BFS) and depthfirst search (DFS) in outerplanar graphs, and finding a2separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Morin, Pat and Bose, Prosenjit
 Abstract:
 We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Peleg, David, Krizanc, Danny, Kirousis, Lefteris M., Kranakis, Evangelos, Kaklamanis, Christos, and Bose, Prosenjit
 Abstract:
 In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius r, r < R, such that the signal originating from the center of the station is so strong that human habitation within distance r from the center p should be avoided. Thus every station determines a region which is an “annulus of permissible habitation". We consider the following station layout (SL) problem: Cover a given (say, rectangular) planar region which includes a collection of orthogonal buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no building is within the dangerous range of a station. We give algorithms for computing such station layouts in both the oneand twodimensional cases.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Krizanc, Danny, Kranakis, Evangelos, and Kirousis, Lefteris M.
 Abstract:
 Let φ be a random Boolean formula that is an instance of 3SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that κ 3.
 Date Created:
 19960101

 Resource Type:
 Conference Proceeding
 Creator:
 Maheshwari, Anil, Sack, JörgRüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
 Date Created:
 19980101

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit and Van Renssen, André
 Abstract:
 We present tight upper and lower bounds on the spanning ratio of a large family of constrained θgraphs. We show that constrained θgraphs with 4k2 (k≥ 1 and integer) cones have a tight spanning ratio of 1+2 sin(θ/2), where θ is 2 π/ (4k+2). We also present improved upper bounds on the spanning ratio of the other families of constrained θgraphs.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 Seidel, Raimund, Dehne, Frank, and Klein, Rolf
 Abstract:
 Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there is at most one local maximum.
 Date Created:
 20021201

 Resource Type:
 Conference Proceeding
 Creator:
 Mannan, Mohammad, Barrera, David, Van Oorschot, Paul C., Lie, David, and Brown, Carson D.
 Abstract:
 Instead of allowing the recovery of original passwords, forgotten passwords are often reset using online mechanisms such as password verification questions (PVQ methods) and password reset links in email. These mechanisms are generally weak, exploitable, and force users to choose new passwords. Emailing the original password exposes the password to third parties. To address these issues, and to allow forgotten passwords to be securely restored, we present a scheme called Mercury. Its primary mode employs userlevel public keys and a personal mobile device (PMD) such as a smartphone, netbook, or tablet. A user generates a key pair on her PMD; the private key remains on the PMD and the public key is shared with different sites (e.g., during account setup). For password recovery, the site sends the (public key)encrypted password to the user's preregistered email address, or displays the encrypted password on a webpage, e.g., as a barcode. The encrypted password is then decrypted using the PMD and revealed to the user. A prototype implementation of Mercury is available as an Android application.
 Date Created:
 20120221

 Resource Type:
 Conference Proceeding
 Creator:
 Van Walderveen, Freek, Davoodi, Pooya, and Smid, Michiel
 Abstract:
 Given a set of n points in the plane, range diameter queries ask for the furthest pair of points in a given axisparallel rectangular range. We provide evidence for the hardness of designing spaceefficient data structures that support range diameter queries by giving a reduction from the set intersection problem. The difficulty of the latter problem is widely acknowledged and is conjectured to require nearly quadratic space in order to obtain constant query time, which is matched by known data structures for both problems, up to polylogarithmic factors. We strengthen the evidence by giving a lower bound for an important subproblem arising in solutions to the range diameter problem: computing the diameter of two convex polygons, that are separated by a vertical line and are preprocessed independently, requires almost linear time in the number of vertices of the smaller polygon, no matter how much space is used. We also show that range diameter queries can be answered much more efficiently for the case of points in convex position by describing a data structure of size O(n log n) that supports queries in O(log n) time.
 Date Created:
 20120515

 Resource Type:
 Conference Proceeding
 Creator:
 Cervera, Gimer, Barbeau, Michel, GarciaAlfaro, Joaquin, and Kranakis, Evangelos
 Abstract:
 The Hierarchical Optimized Link State Routing (HOLSR) protocol enhances the scalability and heterogeneity of traditional OLSRbased Mobile AdHoc Networks (MANETs). It organizes the network in logical levels and nodes in clusters. In every cluster, it implements the mechanisms and algorithms of the original OLSR to generate and to distribute control traffic information. However, the HOLSR protocol was designed with no security in mind. Indeed, it both inherits, from OLSR, and adds new security threats. For instance, the existence of misbehaving nodes can highly affect important HOLSR operations, such as the cluster formation. Cluster IDentification (CID) messages are implemented to organize a HOLSR network in clusters. In every message, the hop count field indicates to the receiver the distance in hops to the originator. An attacker may maliciously alter the hop count field. As a consequence, a receiver node may join a cluster head farther away than it appears. Then, the scalability properties in a HOLSR network is affected by an unbalanced distribution of nodes per cluster. We present a solution based on the use of hash chains to protect mutable fields in CID messages. As a consequence, when a misbehaving node alters the hop count field in a CID message, the receiver nodes are able of detecting and discarding the invalid message.
 Date Created:
 20120127

 Resource Type:
 Conference Proceeding
 Creator:
 Czyzowicz, Jurek, Opatrny, Jaroslav, Kranakis, Evangelos, Narayanan, Lata, Krizanc, Danny, Stacho, Ladislav, Urrutia, Jorge, Yazdani, Mohammadreza, and Lambadaris, Ioannis
 Abstract:
 A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned.
 Date Created:
 20101213

 Resource Type:
 Conference Proceeding
 Creator:
 Barbeau, Michel, Kranakis, Evangelos, and GarciaAlfaro, Joaquin
 Abstract:
 The design and implementation of security threat mitigation mechanisms in RFID systems, specially in lowcost RFID tags, are gaining great attention in both industry and academia. One main focus of research interests is the authentication and privacy techniques to prevent attacks targeting the insecure wireless channel of these systems. Cryptography is a key tool to address these threats. Nevertheless, strong hardware constraints, such as production costs, power consumption, time of response, and regulations compliance, makes the use of traditional cryptography in these systems a very challenging problem. The use of lowoverhead procedures becomes the main approach to solve these challenging problems where traditional cryptography cannot fit. Recent results and trends, with an emphasis on lightweight techniques for addressing critical threats against lowcost RFID systems, are surveyed.
 Date Created:
 20100503

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos, Krizanc, Danny, Narayanan, Lata, and Keane, Michael
 Abstract:
 Delay (or disruption) tolerant sensor networks may be modeled as Markovian evolving graphs [1]. We present experimental evidence showing that considering multiple (possibly not shortest) paths instead of one fixed (greedy) path can decrease the expected time to deliver a packet on such a network by as much as 65 per cent depending on the probability that an edge exists in a given time interval. We provide theoretical justification for this result by studying a special case of the Markovian evolving grid graph. We analyze a natural algorithm for routing on such networks and show that it is possible to improve the expected time of delivery by up to a factor of two depending upon the probability of an edge being up during a time step and the relative positions of the source and destination. Furthermore we show that this is optimal, i.e., no other algorithm can achieve a better expected running time. As an aside, our results give high probability bounds for Knuth's toilet paper problem [11].
 Date Created:
 20091201

 Resource Type:
 Conference Proceeding
 Creator:
 He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
 Date Created:
 20091201

 Resource Type:
 Conference Proceeding
 Creator:
 Krizanc, D., Yazdani, M., Stacho, L., Narayanan, L., Lambadaris, Ioannis, Opatrny, J., Czyzowicz, J., Kranakis, Evangelos, and Urrutia, J.
 Abstract:
 We consider n mobile sensors located on a line containing a barrier represented by a finite line segment. Sensors form a wireless sensor network and are able to move within the line. An intruder traversing the barrier can be detected only when it is within the sensing range of at least one sensor. The sensor network establishes barrier coverage of the segment if no intruder can penetrate the barrier from any direction in the plane without being detected. Starting from arbitrary initial positions of sensors on the line we are interested in finding final positions of sensors that establish barrier coverage and minimize the maximum distance traversed by any sensor. We distinguish several variants of the problem, based on (a) whether or not the sensors have identical ranges, (b) whether or not complete coverage is possible and (c) in the case when complete coverage is impossible, whether or not the maximal coverage is required to be contiguous. For the case of n sensors with identical range, when complete coverage is impossible, we give linear time optimal algorithms that achieve maximal coverage, both for the contiguous and noncontiguous case. When complete coverage is possible, we give an O(n 2) algorithm for an optimal solution, a linear time approximation scheme with approximation factor 2, and a (1∈+∈ε) PTAS. When the sensors have unequal ranges we show that a variation of the problem is NPcomplete and identify some instances which can be solved with our algorithms for sensors with unequal ranges.
 Date Created:
 20091019

 Resource Type:
 Conference Proceeding
 Creator:
 Barbeau, Michel and Laurendeau, Christine
 Abstract:
 Increasingly ubiquitous wireless technologies require novel localization techniques to pinpoint the position of an uncooperative node, whether the target be a malicious device engaging in a security exploit or a lowbattery handset in the middle of a critical emergency. Such scenarios necessitate that a radio signal source be localized by other network nodes efficiently, using minimal information. We propose two new algorithms for estimating the position of an uncooperative transmitter, based on the received signal strength (RSS) of a single target message at a set of receivers whose coordinates are known. As an extension to the concept of centroid localization, our mechanisms weigh each receiver's coordinates based on the message's relative RSS at that receiver, with respect to the span of RSS values over all receivers. The weights may decrease from the highest RSS receiver either linearly or exponentially. Our simulation results demonstrate that for all but the most sparsely populated wireless networks, our exponentially weighted mechanism localizes a target node within the regulations stipulated for emergency services location accuracy.
 Date Created:
 20090928

 Resource Type:
 Conference Proceeding
 Creator:
 Dillabaugh, Craig, He, Meng, and Maheshwari, Anil
 Abstract:
 We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottomup traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottomup path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for topdown traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while topdown traversal can still be performed in an asymptotically optimal number of I/Os.
 Date Created:
 20081201

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos and Wiese, Andreas
 Abstract:
 We investigate the problem of locally coloring and constructing special spanners of location aware Unit Disk Graphs (UDGs). First we present a local approximation algorithm for the vertex coloring problem in UDGs which uses at most four times as many colors as required by an optimal solution. Then we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4colorable spanner of a unit disk graph. The output consists of the spanner and the 4coloring. The computed spanner also has the properties that it is planar, the degree of a vertex in the spanner is at most 5 and the angles between two edges are at least π/3. By enlarging the locality distance (i.e. the size of the neighborhood which a vertex has to explore in order to compute its color) we can ensure the total weight of the spanner to be arbitrarily close to the weight of a minimum spanning tree. We prove that a local algorithm cannot compute a bipartite spanner of a unit disk graph and therefore our algorithm needs at most one color more than any local algorithm for the task requires. Moreover, we prove that there is no local algorithm for 3coloring UDGs or spanners of UDGs, even if the 3colorability of the graph (or the spanner respectively) is guaranteed in advance.
 Date Created:
 20081201

 Resource Type:
 Conference Proceeding
 Creator:
 Petriu, Dorina C. and Tawhid, Rasha
 Abstract:
 The paper proposes to integrate performance analysis in the early phases of the modeldriven development process for Software Product Lines (SPL). We start by adding generic performance annotations to the UML model representing the set of core reusable SPL assets. The annotations are generic and use the MARTE Profile recently adopted by OMG. A first model transformation realized in the Atlas Transformation Language (ATL), which is the focus of this paper, derives the UML model of a specific product with concrete MARTE performance annotations from the SPL model. A second transformation generates a Layered Queueing Network performance model for the given product by applying an existing transformation approach named PUMA, developed in previous work. The proposed technique is illustrated with an ecommerce case study that models the commonality and variability in both structural and behavioural SPL views. A product is derived and the performance of two design alternatives is compared.
 Date Created:
 20081128

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
 Abstract:
 It is wellknown that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in ddimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
 Date Created:
 20081027

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos, Shi, Q., Bhattacharya, B., Wiese, A., Burmester, B., and Hu, Y.
 Abstract:
 Intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. They can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. We consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. We discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.
 Date Created:
 20080922

 Resource Type:
 Conference Proceeding
 Creator:
 Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
 Abstract:
 Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)spanner for P that has O(P) edges and chromatic number at most k. Finally, we consider an online variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
 Date Created:
 20080827