OpenRaiser/Intern-Atlas huggingface dataset:
Strong direct product theorems for quantum communication and query complexity
Venue: arXiv cs.CC 2010
Year: 2010

A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability exp(-Omega(n)). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.
On the Configuration-LP for Scheduling on Unrelated Machines
Venue: arXiv cs.DM 2010
Year: 2010

One of the most important open problems in machine scheduling is the problem of scheduling a set of jobs on unrelated machines to minimize the makespan. The best known approximation algorithm for this problem guarantees an approximation factor of 2. It is known to be NP-hard to approximate with a better ratio than 3/2. Closing this gap has been open for over 20 years. The best known approximation factors are achieved by LP-based algorithms. The strongest known linear program formulation for the problem is the configuration-LP. We show that the configuration-LP has an integrality gap of 2 even for the special case of unrelated graph balancing, where each job can be assigned to at most two machines. In particular, our result implies that a large family of cuts does not help to diminish the integrality gap of the canonical assignment-LP. Also, we present cases of the problem which can be approximated with a better factor than 2. They constitute valuable insights for constructing an NP-hardness reduction which improves the known lower bound. Very recently Svensson studied the restricted assignment case, where each job can only be assigned to a given set of machines on which it has the same processing time. He shows that in this setting the configuration-LP has an integrality gap of 33/17<2. Hence, our result imply that the unrelated graph balancing case is significantly more complex than the restricted assignment case. Then we turn to another objective function: maximizing the minimum machine load. For the case that every job can be assigned to at most two machines we give a purely combinatorial 2-approximation algorithm which is best possible, unless P=NP. This improves on the computationally costly LP-based (2+eps)-approximation algorithm by Chakrabarty et al.
Performance Comparison of Link, Node and Zone Disjoint Multi-path Routing Strategies and Minimum Hop Single Path Routing for Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

The high-level contribution of this paper is a simulation-based analysis to evaluate the tradeoffs between lifetime and hop count of link-disjoint, node-disjoint and zone-disjoint multi-path routes vis-à-vis single-path minimum hop routes for mobile ad hoc networks. The link-disjoint, node-disjoint and zone-disjoint algorithms proposed in this paper can be used to arrive at benchmarks for the time between successive multi-path route discoveries, the number of disjoint paths per multi-path set and the hop count per multi-path set. We assume a multi-path set exists as long as at least one path in the set exists. Simulation results indicate that the number of zone-disjoint paths per multi-path set can be at most 2, which is far lower than the number of node and link-disjoint paths available per multi-path set. Also, the time between zone-disjoint multi-path discoveries would be far lower than the time between node and link-disjoint multi-path route discoveries and can be at most 45% more than the time between single minimum-hop path route discoveries. However, there is no appreciable difference in the average hop counts per zone-disjoint, node-disjoint and link-disjoint multi-path sets and it can be only at most 15% more than the average minimum hop count determined using single-path routing. We also observe that even though the number of link-disjoint paths per multi-path set can be as large as 35-78% more than the number of node-disjoint paths per multi-path set, the time between two successive link-disjoint multi-path discoveries can be at most 15-25% more than the time between two successive node-disjoint multi-path discoveries, without any significant difference in the hop count per multi-path set.
A Coder-Decoder model for use in Lossless Data Compression
Venue: arXiv cs.IT 2010
Year: 2010

This article describes a technique of using a trigonometric function and combinatorial calculations to code or transform any finite sequence of binary numbers (0s and 1s) of any length to a unique set of three Real numbers. In reverse, these three Real numbers can be used independently to reconstruct the original Binary sequence precisely. The main principles of this technique are then applied in a proposal for a highly efficient model for Lossless Data Compression.
GDB: Group Distance Bounding Protocols
Venue: arXiv cs.CR 2010
Year: 2010

Secure distance bounding (DB) protocols allow one entity, the verifier, to securely obtain an upper-bound on the distance to another entity, the prover. Thus far, DB was considered mostly in the context of a single prover and a single verifier. There has been no substantial prior work on secure DB in group settings, where a set of provers interact with a set of verifiers. The need for group distance bounding (GDB) is motivated by many practical scenarios, including: group device pairing, location-based access control and secure distributed localization. GDB is also useful in mission-critical networks and automotive computer systems. This paper addresses, for the first time, GDB protocols by utilizing the new passive DB primitive and the novel mutual multi-party GDB protocol. We show how they can be used to construct secure and efficient GDB protocols for various settings. We analyze security and performance of our protocols and compare them with existing DB techniques when applied to group settings.
Spectrum Sharing as Spatial Congestion Games
Venue: arXiv cs.GT 2010
Year: 2010

In this paper, we present and analyze the properties of a new class of games - the spatial congestion game (SCG), which is a generalization of the classical congestion game (CG). In a classical congestion game, multiple users share the same set of resources and a user's payoff for using any resource is a function of the total number of users sharing it. As a potential game, this game enjoys some very appealing properties, including the existence of a pure strategy Nash equilibrium (NE) and that every improvement path is finite and leads to such a NE (also called the finite improvement property or FIP). While it's tempting to use this model to study spectrum sharing, it does not capture the spatial reuse feature of wireless communication, where resources (interpreted as channels) may be reused without increasing congestion provided that users are located far away from each other. This motivates us to study an extended form of the congestion game where a user's payoff for using a resource is a function of the number of its interfering users sharing it. This naturally results in a spatial congestion game (SCG), where users are placed over a network (or a conflict graph). We study fundamental properties of a spatial congestion game; in particular, we seek to answer under what conditions this game possesses the finite improvement property or a Nash equilibrium. We also discuss the implications of these results when applied to wireless spectrum sharing.
Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer Programming Solvers
Venue: arXiv cs.DS 2010
Year: 2010

In the last decade, the power of the state-of-the-art SAT and Integer Programming solvers has dramatically increased. They implement many new techniques and heuristics and since any NP problem can be converted to SAT or ILP instance, we could take advantage of these techniques in general by converting the instance of NP problem to SAT formula or Integer program. A problem we consider, in this proof of concept, is finding a largest clique in a graph. We ran several experiments on large random graphs and compared 3 approaches: Optimised backtrack solution, Translation to SAT and Translation to Integer program. The last one was the fastest one.
Convergence Speed of the Consensus Algorithm with Interference and Sparse Long-Range Connectivity
Venue: arXiv cs.IT 2010
Year: 2010

We analyze the effect of interference on the convergence rate of average consensus algorithms, which iteratively compute the measurement average by message passing among nodes. It is usually assumed that these algorithms converge faster with a greater exchange of information (i.e., by increased network connectivity) in every iteration. However, when interference is taken into account, it is no longer clear if the rate of convergence increases with network connectivity. We study this problem for randomly-placed consensus-seeking nodes connected through an interference-limited network. We investigate the following questions: (a) How does the rate of convergence vary with increasing communication range of each node? and (b) How does this result change when each node is allowed to communicate with a few selected far-off nodes? When nodes schedule their transmissions to avoid interference, we show that the convergence speed scales with $r^{2-d}$, where $r$ is the communication range and $d$ is the number of dimensions. This scaling is the result of two competing effects when increasing $r$: Increased schedule length for interference-free transmission vs. the speed gain due to improved connectivity. Hence, although one-dimensional networks can converge faster from a greater communication range despite increased interference, the two effects exactly offset one another in two-dimensions. In higher dimensions, increasing the communication range can actually degrade the rate of convergence. Our results thus underline the importance of factoring in the effect of interference in the design of distributed estimation algorithms.
Bayesian Modeling of a Human MMORPG Player
Venue: arXiv cs.AI 2010
Year: 2010

This paper describes an application of Bayesian programming to the control of an autonomous avatar in a multiplayer role-playing game (the example is based on World of Warcraft). We model a particular task, which consists of choosing what to do and to select which target in a situation where allies and foes are present. We explain the model in Bayesian programming and show how we could learn the conditional probabilities from data gathered during human-played sessions.
Evolving difficult SAT instances thanks to local search
Venue: arXiv cs.NE 2010
Year: 2010

We propose to use local search algorithms to produce SAT instances which are harder to solve than randomly generated k-CNF formulae. The first results, obtained with rudimentary search algorithms, show that the approach deserves further study. It could be used as a test of robustness for SAT solvers, and could help to investigate how branching heuristics, learning strategies, and other aspects of solvers impact there robustness.
On Short Cuts - or - Fencing in Rectangular Strips
Venue: arXiv cs.CG 2010
Year: 2010

In this paper we consider an isoperimetric inequality for the "free perimeter" of a planar shape inside a rectangular domain, the free perimeter being the length of the shape boundary that does not touch the border of the domain.
A Comparative Study of the Usability of Two Object-oriented Concurrent Programming Languages
Venue: arXiv cs.PL 2010
Year: 2010

Concurrency has been rapidly gaining importance in general-purpose computing, caused by the recent turn towards multicore processing architectures. As a result, an increasing number of developers have to learn to write concurrent programs, a task that is known to be hard even for the expert. Language designers are therefore working on languages that promise to make concurrent programming "easier" than using traditional thread libraries. However, the claim that a new language is more usable than another cannot be supported by purely theoretical considerations, but calls for empirical studies. In this paper, we present the design of a study to compare concurrent programming languages with respect to comprehending and debugging existing programs and writing correct new programs. A critical challenge for such a study is avoiding the bias that might be introduced during the training phase and when interpreting participants' solutions. We address these issues by the use of self-study material and an evaluation scheme that exposes any subjective decisions of the corrector, or eliminates them altogether. We apply our design to a comparison of two object-oriented languages for concurrency, multithreaded Java and SCOOP (Simple Concurrent Object-Oriented Programming), in an academic setting. We obtain results in favor of SCOOP even though the study participants had previous training in Java Threads.
Coordinated Transmissions to Direct and Relayed Users in Wireless Cellular Systems
Venue: arXiv cs.IT 2010
Year: 2010

The ideas of wireless network coding at the physical layer promise high throughput gains in wireless systems with relays and multi-way traffic flows. This gain can be ascribed to two principles: (1) joint transmission of multiple communication flows and (2) usage of \emph{a priori} information to cancel the interference. In this paper we use these principles to devise new transmission schemes in wireless cellular systems that feature both users served directly by the base stations (direct users) and users served through relays (relayed users). We present four different schemes for \emph{coordinated transmission} of uplink and downlink traffic in which one direct and one relayed user are served. These schemes are then used as building blocks in multi-user scenarios, where we present several schemes for scheduling pairs of users for coordinated transmissions. The optimal scheme involves exhaustive search of the best user pair in terms of overall rate. We propose several suboptimal scheduling schemes, which perform closely to the optimal scheme. The numerical results show a substantial increase in the system--level rate with respect to the systems with non--coordinated transmissions.
Characterizing the speed and paths of shared bicycles in Lyon
Venue: arXiv cs.SI 2010
Year: 2010

Thanks to numerical data gathered by Lyon's shared bicycling system Vélo'v, we are able to analyze 11.6 millions bicycle trips, leading to the first robust characterization of urban bikers' behaviors. We show that bicycles outstrip cars in downtown Lyon, by combining high speed and short paths.These data also allows us to calculate Vélo'v fluxes on all streets, pointing to interesting locations for bike paths.
Expressiveness modulo Bisimilarity of Regular Expressions with Parallel Composition (Extended Abstract)
Venue: arXiv cs.LO 2010
Year: 2010

The languages accepted by finite automata are precisely the languages denoted by regular expressions. In contrast, finite automata may exhibit behaviours that cannot be described by regular expressions up to bisimilarity. In this paper, we consider extensions of the theory of regular expressions with various forms of parallel composition and study the effect on expressiveness. First we prove that adding pure interleaving to the theory of regular expressions strictly increases its expressiveness up to bisimilarity. Then, we prove that replacing the operation for pure interleaving by ACP-style parallel composition gives a further increase in expressiveness. Finally, we prove that the theory of regular expressions with ACP-style parallel composition and encapsulation is expressive enough to express all finite automata up to bisimilarity. Our results extend the expressiveness results obtained by Bergstra, Bethke and Ponse for process algebras with (the binary variant of) Kleene's star operation.
A criterion for separating process calculi
Venue: arXiv cs.LO 2010
Year: 2010

We introduce a new criterion, replacement freeness, to discern the relative expressiveness of process calculi. Intuitively, a calculus is strongly replacement free if replacing, within an enclosing context, a process that cannot perform any visible action by an arbitrary process never inhibits the capability of the resulting process to perform a visible action. We prove that there exists no compositional and interaction sensitive encoding of a not strongly replacement free calculus into any strongly replacement free one. We then define a weaker version of replacement freeness, by only considering replacement of closed processes, and prove that, if we additionally require the encoding to preserve name independence, it is not even possible to encode a non replacement free calculus into a weakly replacement free one. As a consequence of our encodability results, we get that many calculi equipped with priority are not replacement free and hence are not encodable into mainstream calculi like CCS and pi-calculus, that instead are strongly replacement free. We also prove that variants of pi-calculus with match among names, pattern matching or polyadic synchronization are only weakly replacement free, hence they are separated both from process calculi with priority and from mainstream calculi.
Light Logics and Higher-Order Processes
Venue: arXiv cs.LO 2010
Year: 2010

We show that the techniques for resource control that have been developed in the so-called "light logics" can be fruitfully applied also to process algebras. In particular, we present a restriction of Higher-Order pi-calculus inspired by Soft Linear Logic. We prove that any soft process terminates in polynomial time. We argue that the class of soft processes may be naturally enlarged so that interesting processes are expressible, still maintaining the polynomial bound on executions.
Relating timed and register automata
Venue: arXiv cs.FL 2010
Year: 2010

Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave in appearance differently, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance. This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton, and conversely that a run of a register automaton can be simulated by a timed automaton. Our results allow to transfer complexity and decidability results back and forth between these two kinds of models. We justify the usefulness of these reductions by obtaining new results on register automata.
Robustness of Equations Under Operational Extensions
Venue: arXiv cs.LO 2010
Year: 2010

Sound behavioral equations on open terms may become unsound after conservative extensions of the underlying operational semantics. Providing criteria under which such equations are preserved is extremely useful; in particular, it can avoid the need to repeat proofs when extending the specified language. This paper investigates preservation of sound equations for several notions of bisimilarity on open terms: closed-instance (ci-)bisimilarity and formal-hypothesis (fh-)bisimilarity, both due to Robert de Simone, and hypothesis-preserving (hp-)bisimilarity, due to Arend Rensink. For both fh-bisimilarity and hp-bisimilarity, we prove that arbitrary sound equations on open terms are preserved by all disjoint extensions which do not add labels. We also define slight variations of fh- and hp-bisimilarity such that all sound equations are preserved by arbitrary disjoint extensions. Finally, we give two sets of syntactic criteria (on equations, resp. operational extensions) and prove each of them to be sufficient for preserving ci-bisimilarity.
Approximate Shortest Path through a Weighted Planar Subdivision
Venue: arXiv cs.CG 2010
Year: 2010

This paper presents an approximation algorithm for finding a shortest path between two points $s$ and $t$ in a weighted planar subdivision $\PS$. Each face $f$ of $\PS$ is associated with a weight $w_f$, and the cost of travel along a line segment on $f$ is $w_f$ multiplied by the Euclidean norm of that line segment. The cost of a path which traverses across several faces of the subdivision is the sum of the costs of travel along each face. Our algorithm progreeses the discretized shortest path wavefront from source $s$, and takes polynomial time in finding an $ε$-approximate shortest path.
Interference Alignment via Improved Subspace Conditioning
Venue: arXiv cs.IT 2010
Year: 2010

For the K user, single input single output (SISO), frequency selective interference channel, a new low complexity transmit beamforming design that improves the achievable sum rate is presented. Jointly employing the interference alignment (IA) scheme presented by Cadambe and Jafar in [1] and linear minimum mean square error (MMSE) decoding at the transmitters and receivers, respectively, the new IA precoding design improves the average sum rate while preserving the achievable degrees of freedom of the Cadambe and Jafar scheme, K/2.
Secure Wireless Communication and Optimal Power Control under Statistical Queueing Constraints
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, secure transmission of information over fading broadcast channels is studied in the presence of statistical queueing constraints. Effective capacity is employed as a performance metric to identify the secure throughput of the system, i.e., effective secure throughput. It is assumed that perfect channel side information (CSI) is available at both the transmitter and the receivers. Initially, the scenario in which the transmitter sends common messages to two receivers and confidential messages to one receiver is considered. For this case, effective secure throughput region, which is the region of constant arrival rates of common and confidential messages that can be supported by the buffer-constrained transmitter and fading broadcast channel, is defined. It is proven that this effective throughput region is convex. Then, the optimal power control policies that achieve the boundary points of the effective secure throughput region are investigated and an algorithm for the numerical computation of the optimal power adaptation schemes is provided. Subsequently, the special case in which the transmitter sends only confidential messages to one receiver, is addressed in more detail. For this case, effective secure throughput is formulated and two different power adaptation policies are studied. In particular, it is noted that opportunistic transmission is no longer optimal under buffer constraints and the transmitter should not wait to send the data at a high rate until the main channel is much better than the eavesdropper channel.