OpenRaiser/Intern-Atlas huggingface dataset:
On the Security of ``an efficient and complete remote user authentication scheme''
Venue: arXiv cs.CR 2008
Year: 2008

Recently, Liaw et al. proposed a remote user authentication scheme using smart cards. Their scheme has claimed a number of features e.g. mutual authentication, no clock synchronization, no verifier table, flexible user password change, etc. We show that Liaw et al.'s scheme is completely insecure. By intercepting a valid login message in Liaw et al.'s scheme, any unregistered user or adversary can easily login to the remote system and establish a session key.
Support Vector classifiers for Land Cover Classification
Venue: arXiv cs.NE 2008
Year: 2008

Support vector machines represent a promising development in machine learning research that is not widely used within the remote sensing community. This paper reports the results of Multispectral(Landsat-7 ETM+) and Hyperspectral DAIS)data in which multi-class SVMs are compared with maximum likelihood and artificial neural network methods in terms of classification accuracy. Our results show that the SVM achieves a higher level of classification accuracy than either the maximum likelihood or the neural classifier, and that the support vector machine can be used with small training datasets and high-dimensional data.
Set Covering Problems with General Objective Functions
Venue: arXiv cs.DS 2008
Year: 2008

We introduce a parameterized version of set cover that generalizes several previously studied problems. Given a ground set V and a collection of subsets S_i of V, a feasible solution is a partition of V such that each subset of the partition is included in one of the S_i. The problem involves maximizing the mean subset size of the partition, where the mean is the generalized mean of parameter p, taken over the elements. For p=-1, the problem is equivalent to the classical minimum set cover problem. For p=0, it is equivalent to the minimum entropy set cover problem, introduced by Halperin and Karp. For p=1, the problem includes the maximum-edge clique partition problem as a special case. We prove that the greedy algorithm simultaneously approximates the problem within a factor of (p+1)^1/p for any p in R^+, and that this is the best possible unless P=NP. These results both generalize and simplify previous results for special cases. We also consider the corresponding graph coloring problem, and prove several tractability and inapproximability results. Finally, we consider a further generalization of the set cover problem in which we aim at minimizing the sum of some concave function of the part sizes. As an application, we derive an approximation ratio for a Rent-or-Buy set cover problem.
Improved Approximations for Multiprocessor Scheduling Under Uncertainty
Venue: arXiv cs.DC 2008
Year: 2008

This paper presents improved approximation algorithms for the problem of multiprocessor scheduling under uncertainty, or SUU, in which the execution of each job may fail probabilistically. This problem is motivated by the increasing use of distributed computing to handle large, computationally intensive tasks. In the SUU problem we are given n unit-length jobs and m machines, a directed acyclic graph G of precedence constraints among jobs, and unrelated failure probabilities q_{ij} for each job j when executed on machine i for a single timestep. Our goal is to find a schedule that minimizes the expected makespan, which is the expected time at which all jobs complete. Lin and Rajaraman gave the first approximations for this NP-hard problem for the special cases of independent jobs, precedence constraints forming disjoint chains, and precedence constraints forming trees. In this paper, we present asymptotically better approximation algorithms. In particular, we give an O(loglog min(m,n))-approximation for independent jobs (improving on the previously best O(log n)-approximation). We also give an O(log(n+m) loglog min(m,n))-approximation algorithm for precedence constraints that form disjoint chains (improving on the previously best O(log(n)log(m)log(n+m)/loglog(n+m))-approximation by a (log n/loglog n)^2 factor when n = poly(m). Our algorithm for precedence constraints forming chains can also be used as a component for precedence constraints forming trees, yielding a similar improvement over the previously best algorithms for trees.
Guarding curvilinear art galleries with vertex or point guards
Venue: arXiv cs.CG 2008
Year: 2008

One of the earliest and most well known problems in computational geometry is the so-called art gallery problem. The goal is to compute the minimum possible number guards placed on the vertices of a simple polygon in such a way that they cover the interior of the polygon. In this paper we consider the problem of guarding an art gallery which is modeled as a polygon with curvilinear walls. Our main focus is on polygons the edges of which are convex arcs pointing towards the exterior or interior of the polygon (but not both), named piecewise-convex and piecewise-concave polygons. We prove that, in the case of piecewise-convex polygons, if we only allow vertex guards, $\lfloor\frac{4n}{7}\rfloor-1$ guards are sometimes necessary, and $\lfloor\frac{2n}{3}\rfloor$ guards are always sufficient. Moreover, an $O(n\log{}n)$ time and O(n) space algorithm is described that produces a vertex guarding set of size at most $\lfloor\frac{2n}{3}\rfloor$. When we allow point guards the afore-mentioned lower bound drops down to $\lfloor\frac{n}{2}\rfloor$. In the special case of monotone piecewise-convex polygons we can show that $\lfloor\frac{n}{2}\rfloor$ vertex guards are always sufficient and sometimes necessary; these bounds remain valid even if we allow point guards. In the case of piecewise-concave polygons, we show that $2n-4$ point guards are always sufficient and sometimes necessary, whereas it might not be possible to guard such polygons by vertex guards. We conclude with bounds for other types of curvilinear polygons and future work.
The Opportunistic Transmission of Wireless Worms between Mobile Devices
Venue: arXiv cs.NI 2008
Year: 2008

The ubiquity of portable wireless-enabled computing and communications devices has stimulated the emergence of malicious codes (wireless worms) that are capable of spreading between spatially proximal devices. The potential exists for worms to be opportunistically transmitted between devices as they move around, so human mobility patterns will have an impact on epidemic spread. The scenario we address in this paper is proximity attacks from fleetingly in-contact wireless devices with short-range communication range, such as Bluetooth-enabled smart phones. An individual-based model of mobile devices is introduced and the effect of population characteristics and device behaviour on the outbreak dynamics is investigated. We show through extensive simulations that in the above scenario the resulting mass-action epidemic models remain applicable provided the contact rate is derived consistently from the underlying mobility model. The model gives useful analytical expressions against which more refined simulations of worm spread can be developed and tested.
Optimal Medium Access Protocols for Cognitive Radio Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper focuses on the design of medium access control protocols for cognitive radio networks. The scenario in which a single cognitive user wishes to opportunistically exploit the availability of empty frequency bands within parts of the radio spectrum having multiple bands is first considered. In this scenario, the availability probability of each channel is unknown a priori to the cognitive user. Hence efficient medium access strategies must strike a balance between exploring (learning) the availability probability of the channels and exploiting the knowledge of the availability probability identified thus far. For this scenario, an optimal medium access strategy is derived and its underlying recursive structure is illustrated via examples. To avoid the prohibitive computational complexity of this optimal strategy, a low complexity asymptotically optimal strategy is developed. Next, the multi-cognitive user scenario is considered and low complexity medium access protocols, which strike an optimal balance between exploration and exploitation in such competitive environments, are developed.
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Venue: arXiv cs.DS 2008
Year: 2008

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class $AC^1$. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to $UL \cap coUL$. As a consequence of our method we get that the isomorphism problem for oriented graphs is in $NL$. We also show that the problems are hard for $L$.
Efficient Minimization of DFAs with Partial Transition Functions
Venue: arXiv cs.IT 2008
Year: 2008

Let PT-DFA mean a deterministic finite automaton whose transition relation is a partial function. We present an algorithm for minimizing a PT-DFA in $O(m \lg n)$ time and $O(m+n+α)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $α$ is the size of the alphabet. Time consumption does not depend on $α$, because the $α$ term arises from an array that is accessed at random and never initialized. It is not needed, if transitions are in a suitable order in the input. The algorithm uses two instances of an array-based data structure for maintaining a refinable partition. Its operations are all amortized constant time. One instance represents the classical blocks and the other a partition of transitions. Our measurements demonstrate the speed advantage of our algorithm on PT-DFAs over an $O(αn \lg n)$ time, $O(αn)$ memory algorithm.
Minimizing Flow Time in the Wireless Gathering Problem
Venue: arXiv cs.DS 2008
Year: 2008

We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than $Ω(m^{1/3)$ when $m$ packets have to be transmitted, unless $P = NP$. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.
Weak index versus Borel rank
Venue: arXiv cs.IT 2008
Year: 2008

We investigate weak recognizability of deterministic languages of infinite trees. We prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, we propose a procedure computing for a deterministic automaton an equivalent minimal index weak automaton with a quadratic number of states. The algorithm works within the time of solving the emptiness problem.
On Dynamic Breadth-First Search in External-Memory
Venue: arXiv cs.DS 2008
Year: 2008

We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and O(n) edges and monotone update sequences of either $Θ(n)$ edge insertions or $Θ(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+\sort(n)\cdot \log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $Ω(n/B^{1/2}+\sort(n))$ I/Os.
Lower bounds for adaptive linearity tests
Venue: arXiv cs.CC 2008
Year: 2008

Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by (Blum, Luby and Rubenfeld, 1993), and were later used in the PCP theorem, among other applications. The quality of a linearity test is described by its correctness c - the probability it accepts linear functions, its soundness s - the probability it accepts functions far from linear, and its query complexity q - the number of queries it makes. Linearity tests were studied in order to decrease the soundness of linearity tests, while keeping the query complexity small (for one reason, to improve PCP constructions). Samorodnitsky and Trevisan (Samorodnitsky and Trevisan 2000) constructed the Complete Graph Test, and prove that no Hyper Graph Test can perform better than the Complete Graph Test. Later in (Samorodnitsky and Trevisan 2006) they prove, among other results, that no non-adaptive linearity test can perform better than the Complete Graph Test. Their proof uses the algebraic machinery of the Gowers Norm. A result by (Ben-Sasson, Harsha and Raskhodnikova 2005) allows to generalize this lower bound also to adaptive linearity tests. We also prove the same optimal lower bound for adaptive linearity test, but our proof technique is arguably simpler and more direct than the one used in (Samorodnitsky and Trevisan 2006). We also study, like (Samorodnitsky and Trevisan 2006), the behavior of linearity tests on quadratic functions. However, instead of analyzing the Gowers Norm of certain functions, we provide a more direct combinatorial proof, studying the behavior of linearity tests on random quadratic functions...
New Combinatorial Complete One-Way Functions
Venue: arXiv cs.CC 2008
Year: 2008

In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post Correspondence Problem and prove their completeness. Besides, we present an alternative proof of Levin's result. We also discuss the properties a combinatorial problem should have in order to hold a complete one-way function.
Model Checking Games for the Quantitative mu-Calculus
Venue: arXiv cs.LO 2008
Year: 2008

We investigate quantitative extensions of modal logic and the modal mu-calculus, and study the question whether the tight connection between logic and games can be lifted from the qualitative logics to their quantitative counterparts. It turns out that, if the quantitative mu-calculus is defined in an appropriate way respecting the duality properties between the logical operators, then its model checking problem can indeed be characterised by a quantitative variant of parity games. However, these quantitative games have quite different properties than their classical counterparts, in particular they are, in general, not positionally determined. The correspondence between the logic and the games goes both ways: the value of a formula on a quantitative transition system coincides with the value of the associated quantitative game, and conversely, the values of quantitative parity games are definable in the quantitative mu-calculus.
Ni-MH battery modelling for ambient intelligence applications
Venue: arXiv cs.OH 2008
Year: 2008

Mobile devices, like sensor networks and MEMS actuators use mobile power supplies to ensure energy for their operation. These are mostly batteries. The lifetime of the devices depends on the power consumption and on the quality and capacitance of the battery. Though the integrated circuits and their power consumption improve continually, their clock frequency also increases with the time, and the resultant power consumption seems not to vary, or slightly increase. On the other hand, the properties of batteries are developing much slower, necessitating the optimization of their usage on system level.
Parameter Identification of Pressure Sensors by Static and Dynamic Measurements
Venue: arXiv cs.OH 2008
Year: 2008

Fast identification methods of pressure sensors are investigated. With regard to a complete accurate sensor parameter identification two different measurement methods are combined. The approach consists on one hand in performing static measurements - an applied pressure results in a membrane deformation measured interferometrically and the corresponding output voltage. On the other hand optical measurements of the modal responses of the sensor membranes are performed. This information is used in an inverse identification algorithm to identify geometrical and material parameters based on a FE model. The number of parameters to be identified is thereby generally limited only by the number of measurable modal frequencies. A quantitative evaluation of the identification results permits furthermore the classification of processing errors like etching errors. Algorithms and identification results for membrane thickness, intrinsic stress and output voltage will be discussed in this contribution on the basis of the parameter identification of relative pressure sensors.
Design and Modeling of Micromechanical GaAs based Hot Plate for Gas Sensors
Venue: arXiv cs.OH 2008
Year: 2008

For modern Gas sensors, high sensitivity and low power are expected. This paper discusses design, simulation and fabrication of new Micromachined Thermal Converters (MTCs) based on GaAs developed for Gas sensors. Metal oxide gas sensors generally work in high temperature mode that is required for chemical reactions to be performed between molecules of the specified gas and the surface of sensing material. There is a low power consumption required to obtain the operation temperatures in the range of 200 to 500 oC. High thermal isolation of these devices solves consumption problem and can be made by designing of free standing micromechanical hot plates. Mechanical stability and a fast thermal response are especially significant parameters that can not be neglected. These characteristics can be achieved with new concept of GaAs thermal converter.
A Two-Step Etching Method to Fabricate Nanopores in Silicon
Venue: arXiv cs.OH 2008
Year: 2008

A cost effectively method to fabricate nanopores in silicon by only using the conventional wet-etching technique is developed in this research. The main concept of the proposed method is a two-step etching process, including a premier double-sided wet etching and a succeeding track-etching. A special fixture is designed to hold the pre-etched silicon wafer inside it such that the track-etching can be effectively carried out. An electrochemical system is employed to detect and record the ion diffusion current once the pre-etched cavities are etched into a through nanopore. Experimental results indicate that the proposed method can cost effectively fabricate nanopores in silicon.
Noise and thermal stability of vibrating micro-gyrometers preamplifiers
Venue: arXiv cs.OH 2008
Year: 2008

The preamplifier is a critical component of gyrometer's electronics. Indeed the resolution of the sensor is limited by its signal to noise ratio, and the gyrometer's thermal stability is limited by its gain drift. In this paper, five different kinds of preamplifiers are presented and compared. Finally, the design of an integrated preamplifier is shown in order to increase the gain stability while reducing its noise and size.
Interconnect Challenges in Highly Integrated MEMS/ASIC Subsystems
Venue: arXiv cs.OH 2008
Year: 2008

Micromechanical devices like accelerometers or rotation sensors form an increasing segment beneath the devices supplying the consumer market. A hybrid integration approach to build smart sensor clusters for the precise detection of movements in all spatial dimensions requires a large toolbox of interconnect technologies, each with its own constraints regarding the total process integration. Specific challenges described in this paper are post-CMOS feedthroughs, front-to-front die contact arrays, vacuum-compliant lateral interconnect and fine-pitch solder balling to finally form a Chip-Scale System-in-Package (CSSiP).
Nanobiosensors based on individual olfactory receptors
Venue: arXiv cs.OH 2008
Year: 2008

In the SPOT-NOSED European project, nanoscale sensing elements bearing olfactory receptors and grafted onto functionalized gold substrates are used as odorant detectors to develop a new concept of nanobioelectronic nose, through sensitive impedancemetric measurement of single receptor conformational change upon ligand binding, with a better specificity and lower detection threshold than traditional physical sensors.
Online Sensor Testing through Superposition of Encoded Stimulus
Venue: arXiv cs.OH 2008
Year: 2008

Online monitoring remains an important requirement for a range of microsystems. The solution based on the injection of an actuating test stimulus into the bias structure of active devices holds great potential. This paper presents an improved solution that aims to remove the measurand-induced signal from the sensor output. It involves encoding the test stimulus and using a covariance algorithm to reject the signal that does not contain the code. The trade-off between the sine wave rejection ratio of the technique and the test time response is studied and, in the case of a MEMS accelerometer, it is demonstrated that the rejection is higher than 14dB for a test time of about 0.7s. Furthermore, the accuracy of the test signal can be evaluated to guarantee the integrity of the online test output.
Evaluation of the thermal and hydraulic performances of a very thin sintered copper flat heat pipe for 3D microsystem packages
Venue: arXiv cs.OH 2008
Year: 2008

The reported research work presents numerical studies validated by experimental results of a flat micro heat pipe with sintered copper wick structure. The objectives of this project are to produce and demonstrate the efficiency of the passive cooling technology (heat pipe) integrated in a very thin electronic substrate that is a part of a multifunctional 3-D electronic package. The enhanced technology is dedicated to the thermal management of high dissipative microsystems having heat densities of more than 10W/cm2. Future applications are envisaged in the avionics sector. In this research 2D numerical hydraulic model has been developed to investigate the performance of a very thin flat micro heat pipe with sintered copper wick structure, using water as a refrigerant. Finite difference method has been used to develop the model. The model has been used to determine the mass transfer and fluid flow in order to evaluate the limits of heat transport capacity as functions of the dimensions of the wick and the vapour space and for various copper spheres radii. The results are presented in terms of liquid and vapour pressures within the heat pipe. The simulated results are validated by experiments and proved that the method can be further used to predict thermal performance of the heat pipe and to optimise its design.