OpenRaiser/Intern-Atlas huggingface dataset:
A model of protocell based on the introduction of a semi-permeable membrane in a stochastic model of catalytic reaction networks
Venue: arXiv cs.CE 2013
Year: 2013

In this work we introduce some preliminary analyses on the role of a semi-permeable membrane in the dynamics of a stochastic model of catalytic reaction sets (CRSs) of molecules. The results of the simulations performed on ensembles of randomly generated reaction schemes highlight remarkable differences between this very simple protocell description model and the classical case of the continuous stirred-tank reactor (CSTR). In particular, in the CSTR case, distinct simulations with the same reaction scheme reach the same dynamical equilibrium, whereas, in the protocell case, simulations with identical reaction schemes can reach very different dynamical states, despite starting from the same initial conditions.
A Statistical Learning Based System for Fake Website Detection
Venue: arXiv cs.CY 2013
Year: 2013

Existing fake website detection systems are unable to effectively detect fake websites. In this study, we advocate the development of fake website detection systems that employ classification methods grounded in statistical learning theory (SLT). Experimental results reveal that a prototype system developed using SLT-based methods outperforms seven existing fake website detection systems on a test bed encompassing 900 real and fake websites.
Exploration and Exploitation in Visuomotor Prediction of Autonomous Agents
Venue: arXiv cs.LG 2013
Year: 2013

This paper discusses various techniques to let an agent learn how to predict the effects of its own actions on its sensor data autonomously, and their usefulness to apply them to visual sensors. An Extreme Learning Machine is used for visuomotor prediction, while various autonomous control techniques that can aid the prediction process by balancing exploration and exploitation are discussed and tested in a simple system: a camera moving over a 2D greyscale image.
Some issues with Quasi-Steady State Model in Long-term Stability
Venue: arXiv cs.SY 2013
Year: 2013

The Quasi Steady-State (QSS) model of long-term dynamics relies on the idea of time-scale decomposition. Assuming that the fast variables are infinitely fast and are stable in the long-term, the QSS model replaces the differential equations of transient dynamics by their equilibrium equations to reduce complexity and increase computation efficiency. Although the idea of QSS model is intuitive, its theoretical foundation has not yet been developed. In this paper, several counter examples in which the QSS model fails to provide a correct approximation of the complete dynamic model in power system are presented and the reasons of the failure are explained from the viewpoint of nonlinear analysis.
Table-Top Molecular Communication: Text Messages Through Chemical Signals
Venue: arXiv cs.ET 2013
Year: 2013

In this work, we describe the first modular, and programmable platform capable of transmitting a text message using chemical signalling -- a method also known as molecular communication. This form of communication is attractive for applications where conventional wireless systems perform poorly, from nanotechnology to urban health monitoring. Using examples, we demonstrate the use of our platform as a testbed for molecular communication, and illustrate the features of these communication systems using experiments. By providing a simple and inexpensive means of performing experiments, our system fills an important gap in the molecular communication literature, where much current work is done in simulation with simplified system models. A key finding in this paper is that these systems are often nonlinear in practice, whereas current simulations and analysis often assume that the system is linear. However, as we show in this work, despite the nonlinearity, reliable communication is still possible. Furthermore, this work motivates future studies on more realistic modelling, analysis, and design of theoretical models and algorithms for these systems.
Technical report: Functional Constraint Extraction From Register Transfer Level for ATPG
Venue: arXiv cs.AR 2013
Year: 2013

We proposed in "Functional Constraint Extraction From Register Transfer Level for ATPG" that is currently submitted to TVLSI, an automatic functional constraint extractor that can be applied on the RT level. These functional constraints are used to generate pseudo functional test patterns with ATPG tools. The patterns are then used to improve the verification process. This technical report complements the work proposed as it contains the implementation details of the proposed methodology and shows the detailed intermediate and final results of the application of this methodology on a concrete example.
Combinatorial Auctions without Money
Venue: arXiv cs.GT 2013
Year: 2013

Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of $k$-minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.
A Techno-economic Analysis of Network Migration to Software-Defined Networking
Venue: arXiv cs.NI 2013
Year: 2013

As the Software Defined Networking (SDN) paradigm gains momentum, every network operator faces the obvious dilemma: when and how to migrate from existing IP routers to SDN compliant equipments. A single step complete overhaul of a fully functional network is impractical, while at the same time, the immediate benefits of SDN are obvious. A viable solution is thus a gradual migration over time, where questions of which routers should migrate first, and whether the order of migration makes a difference, can be analyzed from techno economic and traffic engineering perspective. In this paper, we address these questions from the techno economic perspective, and establish the importance of migration scheduling. We propose optimization techniques and greedy algorithms to plan an effective migration schedule, based on various techno economic aspects, such as technological gains in combinations with CapEx limitations. We demonstrate the importance of an effective migration sequence through two relevant network management metrics, namely, number of alternative paths availed by a node on migration, and network capacity savings. Our results suggest that the sequence of migration plays a vital role, especially in the early stages of network migration to SDN.
Type refinement and monoidal closed bifibrations
Venue: arXiv cs.LO 2013
Year: 2013

The concept of_refinement_ in type theory is a way of reconciling the "intrinsic" and the "extrinsic" meanings of types. We begin with a rigorous analysis of this concept, settling on the simple conclusion that the type-theoretic notion of "type refinement system" may be identified with the category-theoretic notion of "functor". We then use this correspondence to give an equivalent type-theoretic formulation of Grothendieck's definition of (bi)fibration, and extend this to a definition of_monoidal closed bifibrations_, which we see as a natural space in which to study the properties of proofs and programs. Our main result is a representation theorem for strong monads on a monoidal closed fibration, describing sufficient conditions for a monad to be isomorphic to a continuations monad "up to pullback".
Using the Random Sprays Retinex Algorithm for Global Illumination Estimation
Venue: arXiv cs.CV 2013
Year: 2013

In this paper the use of Random Sprays Retinex (RSR) algorithm for global illumination estimation is proposed and its feasibility tested. Like other algorithms based on the Retinex model, RSR also provides local illumination estimation and brightness adjustment for each pixel and it is faster than other path-wise Retinex algorithms. As the assumption of the uniform illumination holds in many cases, it should be possible to use the mean of local illumination estimations of RSR as a global illumination estimation for images with (assumed) uniform illumination allowing also the accuracy to be easily measured. Therefore we propose a method for estimating global illumination estimation based on local RSR results. To our best knowledge this is the first time that RSR algorithm is used to obtain global illumination estimation. For our tests we use a publicly available color constancy image database for testing. The results are presented and discussed and it turns out that the proposed method outperforms many existing unsupervised color constancy algorithms. The source code is available at http://www.fer.unizg.hr/ipg/resources/color_constancy/.
Global Localization Based on 3D Planar Surface Segments
Venue: arXiv cs.CV 2013
Year: 2013

Global localization of a mobile robot using planar surface segments extracted from depth images is considered. The robot's environment is represented by a topological map consisting of local models, each representing a particular location modeled by a set of planar surface segments. The discussed localization approach segments a depth image acquired by a 3D camera into planar surface segments which are then matched to model surface segments. The robot pose is estimated by the Extended Kalman Filter using surface segment pairs as measurements. The reliability and accuracy of the considered approach are experimentally evaluated using a mobile robot equipped by a Microsoft Kinect sensor.
An Overview and Evaluation of Various Face and Eyes Detection Algorithms for Driver Fatigue Monitoring Systems
Venue: arXiv cs.CV 2013
Year: 2013

In this work various methods and algorithms for face and eyes detection are examined in order to decide which of them are applicable for use in a driver fatigue monitoring system. In the case of face detection the standard Viola-Jones face detector has shown best results, while the method of finding the eye centers by means of gradients has proven to be most appropriate in the case of eyes detection. The later method has also a potential for retrieving behavioral parameters needed for estimation of the level of driver fatigue. This possibility will be examined in future work.
Complexity of Coloring Graphs without Paths and Cycles
Venue: arXiv cs.DM 2013
Year: 2013

Let $P_t$ and $C_\ell$ denote a path on $t$ vertices and a cycle on $\ell$ vertices, respectively. In this paper we study the $k$-coloring problem for $(P_t,C_\ell)$-free graphs. Maffray and Morel, and Bruce, Hoang and Sawada, have proved that 3-colorability of $P_5$-free graphs has a finite forbidden induced subgraphs characterization, while Hoang, Moore, Recoskie, Sawada, and Vatshelle have shown that $k$-colorability of $P_5$-free graphs for $k \geq 4$ does not. These authors have also shown, aided by a computer search, that 4-colorability of $(P_5,C_5)$-free graphs does have a finite forbidden induced subgraph characterization. We prove that for any $k$, the $k$-colorability of $(P_6,C_4)$-free graphs has a finite forbidden induced subgraph characterization. We provide the full lists of forbidden induced subgraphs for $k=3$ and $k=4$. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring $(P_6,C_4)$-free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying); To complement these results we show that in most other cases the $k$-coloring problem for $(P_t,C_\ell)$-free graphs is NP-complete. Specifically, for $\ell=5$ we show that $k$-coloring is NP-complete for $(P_t,C_5)$-free graphs when $k \ge 4$ and $t \ge 7$; for $\ell \ge 6$ we show that $k$-coloring is NP-complete for $(P_t,C_\ell)$-free graphs when $k \ge 5$, $t \ge 6$; and additionally, for $\ell=7$, we show that $k$-coloring is also NP-complete for $(P_t,C_7)$-free graphs if $k = 4$ and $t\ge 9$. This is the first systematic study of the complexity of the $k$-coloring problem for $(P_t,C_\ell)$-free graphs. We almost completely classify the complexity for the cases when $k \geq 4, \ell \geq 4$, and identify the last three open cases.
The Constrained Virtual Steiner Arborescence Problem: Formal Definition, Single-Commodity Integer Programming Formulation and Computational Evaluation
Venue: arXiv cs.NI 2013
Year: 2013

As the Internet becomes more virtualized and software-defined, new functionality is introduced in the network core: the distributed resources available in ISP central offices, universal nodes, or datacenter middleboxes can be used to process (e.g., filter, aggregate or duplicate) data. Based on this new networking paradigm, we formulate the Constrained Virtual Steiner Arborescence Problem (CVSAP) which asks for optimal locations to perform In-network processing, in order to jointly minimize processing costs and network traffic while respecting link and node capacities. We prove that CVSAP cannot be approximated (unless P = NP), and accordingly, develop the exact algorithm VirtuCast to compute (near) optimal solutions. VirtuCast consists of: (1) a compact single-commodity flow Integer Programming (IP) formulation; (2) a flow decomposition algorithm to reconstruct individual routes from the IP solution. The compactness of the IP formulation allows for computing lower bounds even on large instances quickly, speeding up the algorithm. We rigorously prove VirtuCast's correctness. To complement our theoretical findings, we have implemented VirtuCast and present an extensive computational evaluation, showing that using VirtuCast realistically sized instances can be solved (close to) optimality. We show that VirtuCast significantly improves upon naive multi-commodity formulations and also initiate the study of primal heuristics to generate feasible solutions during the branch-and-bound process.
Deep and Wide Multiscale Recursive Networks for Robust Image Labeling
Venue: arXiv cs.CV 2013
Year: 2013

Feedforward multilayer networks trained by supervised learning have recently demonstrated state of the art performance on image labeling problems such as boundary prediction and scene parsing. As even very low error rates can limit practical usage of such systems, methods that perform closer to human accuracy remain desirable. In this work, we propose a new type of network with the following properties that address what we hypothesize to be limiting aspects of existing methods: (1) a `wide' structure with thousands of features, (2) a large field of view, (3) recursive iterations that exploit statistical dependencies in label space, and (4) a parallelizable architecture that can be trained in a fraction of the time compared to benchmark multilayer convolutional networks. For the specific image labeling problem of boundary prediction, we also introduce a novel example weighting algorithm that improves segmentation accuracy. Experiments in the challenging domain of connectomic reconstruction of neural circuity from 3d electron microscopy data show that these "Deep And Wide Multiscale Recursive" (DAWMR) networks lead to new levels of image labeling performance. The highest performing architecture has twelve layers, interwoven supervised and unsupervised stages, and uses an input field of view of 157,464 voxels ($54^3$) to make a prediction at each image location. We present an associated open source software package that enables the simple and flexible creation of DAWMR networks.
On the optimality of approximation schemes for the classical scheduling problem
Venue: arXiv cs.CC 2013
Year: 2013

We consider the classical scheduling problem on parallel identical machines to minimize the makespan, and achieve the following results under the Exponential Time Hypothesis (ETH) 1. The scheduling problem on a constant number $m$ of identical machines, which is denoted as $Pm||C_{max}$, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time $O(n) + (1/ε)^{O(m)}$ (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a $(1/ε)^{O(m^{1-δ})}+n^{O(1)}$ time FPTAS for any $δ>0$ implies that ETH fails. 2. The scheduling problem on an arbitrary number of identical machines, which is denoted as $P||C_{max}$, is known to admit a polynomial time approximation scheme (PTAS) of running time $2^{O(1/ε^2\log^3(1/ε))}+n^{O(1)}$. We prove this algorithm is nearly optimal in the sense that a $2^{O((1/ε)^{1-δ})}+n^{O(1)}$ time PTAS for any $δ>0$ implies that ETH fails, leaving a small room for improvement. To obtain these results we will provide two new reductions from 3SAT, one for $Pm||C_{max}$ and another for $P||C_{max}$. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for $P||C_{max}$, Chen et al. (arXiv:1306.3727) is able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times $P=(p_{ij})_{m\times n}$ is of rank 3, solving the open problem mentioned by Bhaskara et al. (SODA 2013).
Steganography using the Extensible Messaging and Presence Protocol (XMPP)
Venue: arXiv cs.MM 2013
Year: 2013

We present here the first work to propose different mechanisms for hiding data in the Extensible Messaging and Presence Protocol (XMPP). This is a very popular instant messaging protocol used by many messaging platforms such as Google Talk, Cisco, LiveJournal and many others. Our paper describes how to send a secret message from one XMPP client to another, without raising the suspicion of any intermediaries. The methods described primarily focus on using the underlying protocol as a means for steganography, unlike other related works that try to hide data in the content of instant messages. In doing so, we provide a more robust means of data hiding and additionally offer some preliminary analysis of its general security, in particular against entropic-based steganalysis.
Subjective and Objective Evaluation of English to Urdu Machine Translation
Venue: arXiv cs.CL 2013
Year: 2013

Machine translation is research based area where evaluation is very important phenomenon for checking the quality of MT output. The work is based on the evaluation of English to Urdu Machine translation. In this research work we have evaluated the translation quality of Urdu language which has been translated by using different Machine Translation systems like Google, Babylon and Ijunoon. The evaluation process is done by using two approaches - Human evaluation and Automatic evaluation. We have worked for both the approaches where in human evaluation emphasis is given to scales and parameters while in automatic evaluation emphasis is given to some automatic metric such as BLEU, GTM, METEOR and ATEC.
Introducing Enriched Concrete Syntax Trees
Venue: arXiv cs.SE 2013
Year: 2013

In our earlier research an area of consistent and systematic application of software metrics was explored. Strong dependency of applicability of software metrics on input programming language was recognized as one of the main weaknesses in this field. Introducing enriched Concrete Syntax Tree (eCST) for internal and intermediate representation of the source code resulted with step forward over this weakness. In this paper we explain innovation made by introducing eCST and provide idea for broader applicability of eCST in some other fields of software engineering.
Touch-enabled Programming for the Lab of Things
Venue: arXiv cs.PL 2013
Year: 2013

Lab of Things (LoT, lab-of-things.com) is a research platform for interconnection, programming, and large scale deployment of devices and sensors. These devices and sensors can then be used for deployment of field studies in a variety of research areas including elderly care, energy management, and the like. LoT is built on top of HomeOS, a middle-ware component, making interconnection of a wide range of devices possible. LoT also provides cloud storage and remote monitoring capabilities. Traditionally programming on the LoT platform has been done using C# in Microsoft Visual Studio. While LoT programs developed on the .NET framework offer a rich set of functionality, writing programs on LoT can be challenging for developers who are not experienced with the technology involved. In this demonstration, we introduce an innovative programming approach on the LoT platform by building a Generic Application and creating corresponding libraries on the user-friendly TouchDevelop (touchdevelop.com) programming environment. As an example, we implemented the same functionality of the Lab of Things Alerts application using the new Generic App. In addition to a touch-enabled programming environment, the new approach also significantly saves time and effort developers have to devote when creating a customized Lab of Things application.
GOTCHA Password Hackers!
Venue: arXiv cs.CR 2013
Year: 2013

We introduce GOTCHAs (Generating panOptic Turing Tests to Tell Computers and Humans Apart) as a way of preventing automated offline dictionary attacks against user selected passwords. A GOTCHA is a randomized puzzle generation protocol, which involves interaction between a computer and a human. Informally, a GOTCHA should satisfy two key properties: (1) The puzzles are easy for the human to solve. (2) The puzzles are hard for a computer to solve even if it has the random bits used by the computer to generate the final puzzle --- unlike a CAPTCHA. Our main theorem demonstrates that GOTCHAs can be used to mitigate the threat of offline dictionary attacks against passwords by ensuring that a password cracker must receive constant feedback from a human being while mounting an attack. Finally, we provide a candidate construction of GOTCHAs based on Inkblot images. Our construction relies on the usability assumption that users can recognize the phrases that they originally used to describe each Inkblot image --- a much weaker usability assumption than previous password systems based on Inkblots which required users to recall their phrase exactly. We conduct a user study to evaluate the usability of our GOTCHA construction. We also generate a GOTCHA challenge where we encourage artificial intelligence and security researchers to try to crack several passwords protected with our scheme.