OpenRaiser/Intern-Atlas huggingface dataset:
Formulas vs. Circuits for Small Distance Connectivity
Venue: arXiv cs.CC 2013
Year: 2013

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance $k(n)$ Connectivity, which asks whether two specified nodes in a graph of size $n$ are connected by a path of length at most $k(n)$. This problem is solvable (by the recursive doubling technique) on {\bf circuits} of depth $O(\log k)$ and size $O(kn^3)$. In contrast, we show that solving this problem on {\bf formulas} of depth $\log n/(\log\log n)^{O(1)}$ requires size $n^{Ω(\log k)}$ for all $k(n) \leq \log\log n$. As corollaries: (i) It follows that polynomial-size circuits for Distance $k(n)$ Connectivity require depth $Ω(\log k)$ for all $k(n) \leq \log\log n$. This matches the upper bound from recursive doubling and improves a previous $Ω(\log\log k)$ lower bound of Beame, Pitassi and Impagliazzo [BIP98]. (ii) We get a tight lower bound of $s^{Ω(d)}$ on the size required to simulate size-$s$ depth-$d$ circuits by depth-$d$ formulas for all $s(n) = n^{O(1)}$ and $d(n) \leq \log\log\log n$. No lower bound better than $s^{Ω(1)}$ was previously known for any $d(n) \nleq O(1)$. Our proof technique is centered on a new notion of pathset complexity, which roughly speaking measures the minimum cost of constructing a set of (partial) paths in a universe of size $n$ via the operations of union and relational join, subject to certain density constraints. Half of our proof shows that bounded-depth formulas solving Distance $k(n)$ Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity.
Radix Conversion for IEEE754-2008 Mixed Radix Floating-Point Arithmetic
Venue: arXiv cs.MS 2013
Year: 2013

Conversion between binary and decimal floating-point representations is ubiquitous. Floating-point radix conversion means converting both the exponent and the mantissa. We develop an atomic operation for FP radix conversion with simple straight-line algorithm, suitable for hardware design. Exponent conversion is performed with a small multiplication and a lookup table. It yields the correct result without error. Mantissa conversion uses a few multiplications and a small lookup table that is shared amongst all types of conversions. The accuracy changes by adjusting the computing precision.
Analog Baseband Cancellation for Full-Duplex: An Experiment Driven Analysis
Venue: arXiv cs.NI 2013
Year: 2013

Recent wireless testbed implementations have proven that full-duplex communication is in fact possible and can outperform half-duplex systems. Many of these implementations modify existing half-duplex systems to operate in full-duplex. To realize the full potential of full-duplex, radios need to be designed with self-interference in mind. In our work, we use a novel patch antenna prototype in an experimental setup to characterize the self-interference channel between transmit and receive radios. We derive an equivalent analytical baseband model and propose analog baseband cancellation techniques to complement the RF cancellation provided by the patch antenna prototype. Our results show that a wide bandwidth, moderate isolation scheme achieves up to 2.4 bps/Hz higher achievable rate than a narrow bandwidth, high isolation scheme. Furthermore, the analog baseband cancellation yields a 10-10,000 improvement in BER over RF only cancellation.
Fully Automatic Liquid Metal Printer towards Personal Electronics Manufacture
Venue: arXiv cs.ET 2013
Year: 2013

Printed electronics is quickly emerging with tremendous value in a wide variety of latest electrical engineering areas. However, restricted to the rather limited conductive inks and printing strategies, the currently existing electronics manufacturing tools are generally complicated, expensive, time, material, water and energy consuming, and thus mainly restricted to the industrial use. Here from an alternative way, the present article demonstrated for the first time an entirely automatic printing system for personal electronics manufacturing through introducing a composite liquid metal ink delivery and printing mechanism to overcome the large surface tension facing the solution, and integrating it with the notebook computer controlling algorithm. With the developed printer, any desired electronically conductive patterns spanning from single wires to various complex structures like integrated circuit (IC), antenna, PCB, RFID, electronic greeting cards, decoration arts, classical buildings (White House, Great Wall etc.) or more do-it-yourself (DIY) circuits were demonstrated to be printed out in a moment with high precision. And the total cost for the whole system has reached personal affordability, which is hard to offer by so far the state of the art technologies. Some fundamental fluid dynamics mechanisms related to the proposed tapping mode enabled reliable printing and adhesion of the liquid metal electronics on the flexible substrate was systematically disclosed through theoretical interpretation and experimental measurements. This clearly beyond-the-lab technology and pervasively available liquid metal printer opens the way for large scale home level electronics making in the coming time.
Differential Games of Competition in Online Content Diffusion
Venue: arXiv cs.SI 2013
Year: 2013

Access to online contents represents a large share of the Internet traffic. Most such contents are multimedia items which are user-generated, i.e., posted online by the contents' owners. In this paper we focus on how those who provide contents can leverage online platforms in order to profit from their large base of potential viewers. Actually, platforms like Vimeo or YouTube provide tools to accelerate the dissemination of contents, i.e., recommendation lists and other re-ranking mechanisms. Hence, the popularity of a content can be increased by paying a cost for advertisement: doing so, it will appear with some priority in the recommendation lists and will be accessed more frequently by the platform users. Ultimately, such acceleration mechanism engenders a competition among online contents to gain popularity. In this context, our focus is on the structure of the acceleration strategies which a content provider should use in order to optimally promote a content given a certain daily budget. Such a best response indeed depends on the strategies adopted by competing content providers. Also, it is a function of the potential popularity of a content and the fee paid for the platform advertisement service. We formulate the problem as a differential game and we solve it for the infinite horizon case by deriving the structure of certain Nash equilibria of the game.
The Optimal Mechanism in Differential Privacy: Multidimensional Setting
Venue: arXiv cs.CR 2013
Year: 2013

We derive the optimal $ε$-differentially private mechanism for a general two-dimensional real-valued (histogram-like) query function under a utility-maximization (or cost-minimization) framework for the $\ell^1$ cost function. We show that the optimal noise probability distribution has a correlated multidimensional staircase-shaped probability density function. Compared with the Laplacian mechanism, we show that in the high privacy regime (as $ε\to 0$), the Laplacian mechanism is approximately optimal; and in the low privacy regime (as $ε\to +\infty$), the optimal cost is $Θ(e^{-\fracε{3}})$, while the cost of the Laplacian mechanism is $\frac{2Δ}ε$, where $Δ$ is the sensitivity of the query function. We conclude that the gain is more pronounced in the low privacy regime. We conjecture that the optimality of the staircase mechanism holds for vector-valued (histogram-like) query functions with arbitrary dimension, and holds for many other classes of cost functions as well.
A Theory of Changes for Higher-Order Languages - Incrementalizing λ-Calculi by Static Differentiation
Venue: arXiv cs.PL 2013
Year: 2013

If the result of an expensive computation is invalidated by a small change to the input, the old result should be updated incrementally instead of reexecuting the whole computation. We incrementalize programs through their derivative. A derivative maps changes in the program's input directly to changes in the program's output, without reexecuting the original program. We present a program transformation taking programs to their derivatives, which is fully static and automatic, supports first-class functions, and produces derivatives amenable to standard optimization. We prove the program transformation correct in Agda for a family of simply-typed λ-calculi, parameterized by base types and primitives. A precise interface specifies what is required to incrementalize the chosen primitives. We investigate performance by a case study: We implement in Scala the program transformation, a plugin and improve performance of a nontrivial program by orders of magnitude.
A Backstepping Control Method for a Nonlinear Process - Two Coupled-Tanks
Venue: arXiv cs.SY 2013
Year: 2013

The aim of this work is to compute a level backstepping control strategy for a coupled tanks system. The coupled tanks plant is a component included in the water treatment system of power plants. The nonlinear-model of the process was designed and implemented in Matlab- Simulink. The advantages of the control method proposed is that it takes into consideration the nonlinearity which can be useful for stabilization and a larger operating point with specified performances. The backstepping control method is computed using the nonlinear model of the system and the performance was validated on the physical plant.
A generic system for critiquing physicians' prescriptions: usability, satisfaction and lessons learnt
Venue: arXiv cs.AI 2013
Year: 2013

Clinical decision support systems have been developed to help physicians to take clinical guidelines into account during consultations. The ASTI critiquing module is one such systems; it provides the physician with automatic criticisms when a drug prescription does not follow the guidelines. It was initially developed for hypertension and type 2 diabetes, but is designed to be generic enough for application to all chronic diseases. We present here the results of usability and satisfaction evaluations for the ASTI critiquing module, obtained with GPs for a newly implemented guideline concerning dyslipaemia, and we discuss the lessons learnt and the difficulties encountered when building a generic DSS for critiquing physicians' prescriptions.
A semi-automatic semantic method for mapping SNOMED CT concepts to VCM Icons
Venue: arXiv cs.AI 2013
Year: 2013

VCM (Visualization of Concept in Medicine) is an iconic language for representing key medical concepts by icons. However, the use of this language with reference terminologies, such as SNOMED CT, will require the mapping of its icons to the terms of these terminologies. Here, we present and evaluate a semi-automatic semantic method for the mapping of SNOMED CT concepts to VCM icons. Both SNOMED CT and VCM are compositional in nature; SNOMED CT is expressed in description logic and VCM semantics are formalized in an OWL ontology. The proposed method involves the manual mapping of a limited number of underlying concepts from the VCM ontology, followed by automatic generation of the rest of the mapping. We applied this method to the clinical findings of the SNOMED CT CORE subset, and 100 randomly-selected mappings were evaluated by three experts. The results obtained were promising, with 82 of the SNOMED CT concepts correctly linked to VCM icons according to the experts. Most of the errors were easy to fix.
Feature Extraction of Human Lip Prints
Venue: arXiv cs.CV 2013
Year: 2013

Methods have been used for identification of human by recognizing lip prints. Human lips have a number of elevation and depressions features called lip prints and examination of lip prints is referred to as cheiloscopy. Lip prints of each human being are unique in nature like many others features of human. In this paper lip print is first smoothened using a Gaussian Filter. Next Sobel Edge Detector and Canny Edge Detector are used to detect the vertical and horizontal groove pattern in the lip. This method of identification will be useful both in criminal forensics and personal identification. It is our assumption that study of lip prints and their types are well connected to play a song in a better way that are well accepted to people who loves to hear songs.
Impact of Mobile Transmitter Sources on Radio Frequency Wireless Energy Harvesting
Venue: arXiv cs.NI 2013
Year: 2013

Wireless energy harvesting sensor networks constitute a new paradigm, where the motes deployed in the field are no longer constrained by the limited battery resource, but are able to re-charge themselves through directed electromagnetic energy transfer. The energy sources, which we call actors, are mobile and move along pre-decided patterns while radiating an appropriate level of energy, sufficient enough to charge the sensors at an acceptable rate. This is the first work that investigates the impact of energy transfer, especially concerning the energy gain in the sensors, the energy spent by the actors, and the overall lifetime in the resulting mobile sensor-actor networks. We propose two event-specific mobility models, where the events occur at the centers of a Voronoi tessellation, and the actors move along either (i)the edges of the Voronoi cells, or (ii) directly from one event center to another. We undertake a comprehensive simulation based study using traces obtained from our experimental energy harvesting circuits powering Mica2 motes. Our results reveal several non-intuitive outcomes, and provide guidelines on which mobility model may be adopted based on the distribution of the events and actors.
Epidemic Thresholds with External Agents
Venue: arXiv cs.SI 2013
Year: 2013

We study the effect of external infection sources on phase transitions in epidemic processes. In particular, we consider an epidemic spreading on a network via the SIS/SIR dynamics, which in addition is aided by external agents - sources unconstrained by the graph, but possessing a limited infection rate or virulence. Such a model captures many existing models of externally aided epidemics, and finds use in many settings - epidemiology, marketing and advertising, network robustness, etc. We provide a detailed characterization of the impact of external agents on epidemic thresholds. In particular, for the SIS model, we show that any external infection strategy with constant virulence either fails to significantly affect the lifetime of an epidemic, or at best, sustains the epidemic for a lifetime which is polynomial in the number of nodes. On the other hand, a random external-infection strategy, with rate increasing linearly in the number of infected nodes, succeeds under some conditions to sustain an exponential epidemic lifetime. We obtain similar sharp thresholds for the SIR model, and discuss the relevance of our results in a variety of settings.
Impact of Report Message Scheduling (RMS) in 1G/10G EPON and GPON (Extended Version)
Venue: arXiv cs.NI 2013
Year: 2013

A wide array of dynamic bandwidth allocation (DBA) mechanisms have recently been proposed for improving bandwidth utilization and reducing idle times and packets delays in passive optical networks (PONs). The DBA evaluation studies commonly assumed that the report message for communicating the bandwidth demands of the distributed optical network units (ONUs) to the central optical line terminal (OLT) is scheduled for the end of an ONU's upstream transmission, after the ONU's payload data transmissions. In this article, we conduct a detailed investigation of the impact of the report message scheduling (RMS), either at the beginning (i.e., before the pay load data) or the end of an ONU upstream transmission on PON performance. We analytically characterize the reduction in channel idle time with reporting at the beginning of an upstream transmission compared to reporting at the end. Our extensive simulation experiments consider both the Ethernet Passive Optical Networking (EPON) standard and the Gigabit PON (GPON) standard. We find that for DBAs with offline sizing and scheduling of ONU upstream transmission grants at the end of a polling cycle, which processes requests from all ONUs, reporting at the beginning gives substantial reductions of mean packet delay at high loads. For high-performing DBAs with online grant sizing and scheduling, which immediately processes individual ONU requests, or interleaving of ONUs groups, both reporting at the beginning or end give essentially the same average packet delays.
High Throughput Virtual Screening with Data Level Parallelism in Multi-core Processors
Venue: arXiv cs.AI 2013
Year: 2013

Improving the throughput of molecular docking, a computationally intensive phase of the virtual screening process, is a highly sought area of research since it has a significant weight in the drug designing process. With such improvements, the world might find cures for incurable diseases like HIV disease and Cancer sooner. Our approach presented in this paper is to utilize a multi-core environment to introduce Data Level Parallelism (DLP) to the Autodock Vina software, which is a widely used for molecular docking software. Autodock Vina already exploits Instruction Level Parallelism (ILP) in multi-core environments and therefore optimized for such environments. However, with the results we have obtained, it can be clearly seen that our approach has enhanced the throughput of the already optimized software by more than six times. This will dramatically reduce the time consumed for the lead identification phase in drug designing along with the shift in the processor technology from multi-core to many-core of the current era. Therefore, we believe that the contribution of this project will effectively make it possible to expand the number of small molecules docked against a drug target and improving the chances to design drugs for incurable diseases.
A Game Semantics for Generic Polymorphism
Venue: arXiv cs.LO 2013
Year: 2013

Genericity is the idea that the same program can work at many different data types. Longo, Milstead and Soloviev proposed to capture the inability of generic programs to probe the structure of their instances by the following equational principle: if two generic programs, viewed as terms of type $\forall X. \, A[X]$, are equal at any given instance $A[T]$, then they are equal at all instances. They proved that this rule is admissible in a certain extension of System F, but finding a semantically motivated model satisfying this principle remained an open problem. In the present paper, we construct a categorical model of polymorphism, based on game semantics, which contains a large collection of generic types. This model builds on two novel constructions: -- A direct interpretation of variable types as games, with a natural notion of substitution of games. This allows moves in games A[T] to be decomposed into the generic part from A, and the part pertaining to the instance T. This leads to a simple and natural notion of generic strategy. -- A "relative polymorphic product" which expresses quantification over the type variable X in the variable type A with respect to a "universe'" which is explicitly given as an additional parameter B. We then solve a recursive equation involving this relative product to obtain a universe in a suitably "absolute" sense. Full Completeness for ML types (universal closures of quantifier-free types) is proved for this model.
M3: An Open Model for Measuring Code Artifacts
Venue: arXiv cs.SE 2013
Year: 2013

This document details design considerations of M3: a meta model for source code artifacts
The Mellon Fedora Project: Digital Library Architecture Meets XML and Web Services
Venue: arXiv cs.DL 2013
Year: 2013

The University of Virginia received a grant of $1,000,000 from the Andrew W. Mellon Foundation to enable the Library, in collaboration with Cornell University, to build a digital object repository system based on the Flexible Extensible Digital Object and Repository Architecture (Fedora). The new system demonstrates how distributed digital library architecture can be deployed using web-based technologies, including XML and Web services. The new system is designed to be a foundation upon which interoperable web-based digital libraries can be built. Virginia and collaborating partners in the US and UK will evaluate the system using a diverse set of digital collections. The software will be made available to the public as an open-source release.
A Passivity Framework for Modeling and Mitigating Wormhole Attacks on Networked Control Systems
Venue: arXiv cs.SY 2013
Year: 2013

Networked control systems consist of distributed sensors and actuators that communicate via a wireless network. The use of an open wireless medium and unattended deployment leaves these systems vulnerable to intelligent adversaries whose goal is to disrupt the system performance. In this paper, we study the wormhole attack on a networked control system, in which an adversary establishes a link between two distant regions of the network by using either high-gain antennas, as in the out-of-band wormhole, or colluding network nodes as in the in-band wormhole. Wormholes allow the adversary to violate the timing constraints of real-time control systems by delaying or dropping packets, and cannot be detected using cryptographic mechanisms alone. We study the impact of the wormhole attack on the network flows and delays and introduce a passivity-based control-theoretic framework for modeling the wormhole attack. We develop this framework for both the in-band and out-of-band wormhole attacks as well as complex, hereto-unreported wormhole attacks consisting of arbitrary combinations of in-and out-of band wormholes. We integrate existing mitigation strategies into our framework, and analyze the throughput, delay, and stability properties of the overall system. Through simulation study, we show that, by selectively dropping control packets, the wormhole attack can cause disturbances in the physical plant of a networked control system, and demonstrate that appropriate selection of detection parameters mitigates the disturbances due to the wormhole while satisfying the delay constraints of the physical system.
Low Complexity Decoding for Punctured Trellis-Coded Modulation Over Intersymbol Interference Channels
Venue: arXiv cs.IT 2013
Year: 2013

Classical trellis-coded modulation (TCM) as introduced by Ungerboeck in 1976/1983 uses a signal constellation of twice the cardinality compared to an uncoded transmission with one bit of redundancy per PAM symbol, i.e., application of codes with rates $\frac{n-1}{n}$ when $2^{n}$ denotes the cardinality of the signal constellation. The original approach therefore only comprises integer transmission rates, i.e., $R=\left\{ 2,\,3,\,4\,\ldots \right\}$, additionally, when transmitting over an intersymbol interference (ISI) channel an optimum decoding scheme would perform equalization and decoding of the channel code jointly. In this paper, we allow rate adjustment for TCM by means of puncturing the convolutional code (CC) on which a TCM scheme is based on. In this case a nontrivial mapping of the output symbols of the CC to signal points results in a time-variant trellis. We propose an efficient technique to integrate an ISI-channel into this trellis and show that the computational complexity can be significantly reduced by means of a reduced state sequence estimation (RSSE) algorithm for time-variant trellises.