OpenRaiser/Intern-Atlas huggingface dataset:
Stop the Chase
Venue: arXiv cs.DB 2009
Year: 2009

The chase procedure, an algorithm proposed 25+ years ago to fix constraint violations in database instances, has been successfully applied in a variety of contexts, such as query optimization, data exchange, and data integration. Its practicability, however, is limited by the fact that - for an arbitrary set of constraints - it might not terminate; even worse, chase termination is an undecidable problem in general. In response, the database community has proposed sufficient restrictions on top of the constraints that guarantee chase termination on any database instance. In this paper, we propose a novel sufficient termination condition, called inductive restriction, which strictly generalizes previous conditions, but can be checked as efficiently. Furthermore, we motivate and study the problem of data-dependent chase termination and, as a key result, present sufficient termination conditions w.r.t. fixed instances. They are strictly more general than inductive restriction and might guarantee termination although the chase does not terminate in the general case.
Dynamic Control of a Flow-Rack Automated Storage and Retrieval System
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we propose a control scheme based on coloured Petri net (CPN) for a flow-rack automated storage and retrieval system. The AS/RS is modelled using Coloured Petri nets, the developed model has been used to capture and provide the rack state. We introduce in the control system an optimization module as a decision process which performs a real-time optimization working on a discrete events time scale. The objective is to find bin locations for the retrieval requests by minimizing the total number of retrieval cycles for a batch of requests and thereby increase the system throughput. By solving the optimization model, the proposed method gives according to customers request and the rack state, the best bin locations for retrieval, i.e. allowing at the same time to satisfy the customers request and carrying out the minimum of retrieval cycles.
Some Generalizations of the Capacity Theorem for AWGN Channels
Venue: arXiv cs.IT 2009
Year: 2009

The channel capacity theorem for additive white Gaussian noise channel (AWGN), widely known as the Shannon-Hartley Law, expresses the information capacity of a channel bandlimited in the conventional Fourier domain in terms of the signal-to-noise ratio in it. In this letter generalized versions of the Shannon-Hartley Law using the linear canonical transform (LCT) are presented. The channel capacity for AWGN channels is found to be a function of the LCT parameters.
Alpaga: A Tool for Solving Parity Games with Imperfect Information
Venue: arXiv cs.GT 2009
Year: 2009

Alpaga is a solver for two-player parity games with imperfect information. Given the description of a game, it determines whether the first player can ensure to win and, if so, it constructs a winning strategy. The tool provides a symbolic implementation of a recent algorithm based on antichains.
A Knowledge Discovery Framework for Learning Task Models from User Interactions in Intelligent Tutoring Systems
Venue: arXiv cs.AI 2009
Year: 2009

Domain experts should provide relevant domain knowledge to an Intelligent Tutoring System (ITS) so that it can guide a learner during problemsolving learning activities. However, for many ill-defined domains, the domain knowledge is hard to define explicitly. In previous works, we showed how sequential pattern mining can be used to extract a partial problem space from logged user interactions, and how it can support tutoring services during problem-solving exercises. This article describes an extension of this approach to extract a problem space that is richer and more adapted for supporting tutoring services. We combined sequential pattern mining with (1) dimensional pattern mining (2) time intervals, (3) the automatic clustering of valued actions and (4) closed sequences mining. Some tutoring services have been implemented and an experiment has been conducted in a tutoring system.
Space Efficient Secret Sharing: A Recursive Approach
Venue: arXiv cs.CR 2009
Year: 2009

This paper presents a recursive secret sharing technique that distributes k-1 secrets of length b each into n shares such that each share is effectively of length (n/(k-1))*b and any k pieces suffice for reconstructing all the k-1 secrets. Since n/(k-1) is near the optimal factor of n/k, and can be chosen to be close to 1, the proposed technique is space efficient. Furthermore, each share is information theoretically secure, i.e. it does not depend on any unproven assumption of computational intractability. Such a recursive technique has potential applications in secure and reliable storage of information on the Web and in sensor networks.
Cut-Simulation and Impredicativity
Venue: arXiv cs.LO 2009
Year: 2009

We investigate cut-elimination and cut-simulation in impredicative (higher-order) logics. We illustrate that adding simple axioms such as Leibniz equations to a calculus for an impredicative logic -- in our case a sequent calculus for classical type theory -- is like adding cut. The phenomenon equally applies to prominent axioms like Boolean- and functional extensionality, induction, choice, and description. This calls for the development of calculi where these principles are built-in instead of being treated axiomatically.
Bounds on the Size of Small Depth Circuits for Approximating Majority
Venue: arXiv cs.CC 2009
Year: 2009

In this paper, we show that for every constant $0 < ε< 1/2$ and for every constant $d \geq 2$, the minimum size of a depth $d$ Boolean circuit that $ε$-approximates Majority function on $n$ variables is exp$(Θ(n^{1/(2d-2)}))$. The lower bound for every $d \geq 2$ and the upper bound for $d=2$ have been previously shown by O'Donnell and Wimmer [ICALP'07], and the contribution of this paper is to give a matching upper bound for $d \geq 3$.
Over-enhancement Reduction in Local Histogram Equalization using its Degrees of Freedom
Venue: arXiv cs.CV 2009
Year: 2009

A well-known issue of local (adaptive) histogram equalization (LHE) is over-enhancement (i.e., generation of spurious details) in homogenous areas of the image. In this paper, we show that the LHE problem has many solutions due to the ambiguity in ranking pixels with the same intensity. The LHE solution space can be searched for the images having the maximum PSNR or structural similarity (SSIM) with the input image. As compared to the results of the prior art, these solutions are more similar to the input image while offering the same local contrast. Index Terms: histogram modification or specification, contrast enhancement
The acoustic wave equation in the expanding universe. Sachs-Wolfe theorem
Venue: arXiv cs.SC 2009
Year: 2009

In this paper the acoustic field propagating in the early hot ($p=ε/$) universe of arbitrary space curvature ($K=0, \pm 1$) is considered. The field equations are reduced to the d'Alembert equation in an auxiliary static Roberson-Walker space-time. Symbolic computation in {\em Mathematica} is applied.
Stability and Delay of Zero-Forcing SDMA with Limited Feedback
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses the stability and queueing delay of Space Division Multiple Access (SDMA) systems with bursty traffic, where zero-forcing beamforming enables simultaneous transmission to multiple mobiles. Computing beamforming vectors relies on quantized channel state information (CSI) feedback (limited feedback) from mobiles. Define the stability region for SDMA as the set of multiuser packet-arrival rates for which the steady-state queue lengths are finite. Given perfect CSI feedback and equal power allocation over scheduled queues, the stability region is proved to be a convex polytope having the derived vertices. For any set of arrival rates in the stability region, multiuser queues are shown to be stabilized by a joint queue-and-beamforming control policy that maximizes the departure-rate-weighted sum of queue lengths. The stability region for limited feedback is found to be the perfect-CSI region multiplied by one minus a small factor. The required number of feedback bits per mobile is proved to scale logarithmically with the inverse of the above factor as well as linearly with the number of transmit antennas minus one. The effects of limited feedback on queueing delay are also quantified. For Poisson arrival processes, CSI quantization errors are shown to multiply average queueing delay by a factor larger than one. This factor can be controlled by adjusting the number of feedback bits per mobile following the derived relationship. For general arrival processes, CSI errors are found to increase Kingman's bound on the tail probability of the instantaneous delay by one plus a small factor. The required number of feedback bits per mobile is shown to scale logarithmically with this factor.
Non-monotone submodular maximization under matroid and knapsack constraints
Venue: arXiv cs.CC 2009
Year: 2009

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. For the problem of maximizing a non-monotone submodular function, Feige, Mirrokni, and Vondrák recently developed a $2\over 5$-approximation algorithm \cite{FMV07}, however, their algorithms do not handle side constraints.} In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for {\em non-monotone} submodular functions. In particular, for any constant $k$, we present a $({1\over k+2+{1\over k}+ε})$-approximation for the submodular maximization problem under $k$ matroid constraints, and a $({1\over 5}-ε)$-approximation algorithm for this problem subject to $k$ knapsack constraints ($ε>0$ is any constant). We improve the approximation guarantee of our algorithm to ${1\over k+1+{1\over k-1}+ε}$ for $k\ge 2$ partition matroid constraints. This idea also gives a $({1\over k+ε})$-approximation for maximizing a {\em monotone} submodular function subject to $k\ge 2$ partition matroids, which improves over the previously best known guarantee of $\frac{1}{k+1}$.
Optimum Power and Rate Allocation for Coded V-BLAST
Venue: arXiv cs.IT 2009
Year: 2009

An analytical framework for minimizing the outage probability of a coded spatial multiplexing system while keeping the rate close to the capacity is developed. Based on this framework, specific strategies of optimum power and rate allocation for the coded V-BLAST architecture are obtained and its performance is analyzed. A fractional waterfilling algorithm, which is shown to optimize both the capacity and the outage probability of the coded V-BLAST, is proposed. Compact, closed-form expressions for the optimum allocation of the average power are given. The uniform allocation of average power is shown to be near optimum at moderate to high SNR for the coded V-BLAST with the average rate allocation (when per-stream rates are set to match the per-stream capacity). The results reported also apply to multiuser detection and channel equalization relying on successive interference cancelation.
On the complexity of Nash dynamics and Sink Equilibria
Venue: arXiv cs.GT 2009
Year: 2009

Studying Nash dynamics is an important approach for analyzing the outcome of games with repeated selfish behavior of self-interested agents. Sink equilibria has been introduced by Goemans, Mirrokni, and Vetta for studying social cost on Nash dynamics over pure strategies in games. However, they do not address the complexity of sink equilibria in these games. Recently, Fabrikant and Papadimitriou initiated the study of the complexity of Nash dynamics in two classes of games. In order to completely understand the complexity of Nash dynamics in a variety of games, we study the following three questions for various games: (i) given a state in game, can we verify if this state is in a sink equilibrium or not? (ii) given an instance of a game, can we verify if there exists any sink equilibrium other than pure Nash equilibria? and (iii) given an instance of a game, can we verify if there exists a pure Nash equilibrium (i.e, a sink equilibrium with one state)? In this paper, we almost answer all of the above questions for a variety of classes of games with succinct representation, including anonymous games, player-specific and weighted congestion games, valid-utility games, and two-sided market games. In particular, for most of these problems, we show that (i) it is PSPACE-complete to verify if a given state is in a sink equilibrium, (ii) it is NP-hard to verify if there exists a pure Nash equilibrium in the game or not, (iii) it is PSPACE-complete to verify if there exists any sink equilibrium other than pure Nash equilibria. To solve these problems, we illustrate general techniques that could be used to answer similar questions in other classes of games.
Bootstrapped Oblivious Transfer and Secure Two-Party Function Computation
Venue: arXiv cs.CR 2009
Year: 2009

We propose an information theoretic framework for the secure two-party function computation (SFC) problem and introduce the notion of SFC capacity. We study and extend string oblivious transfer (OT) to sample-wise OT. We propose an efficient, perfectly private OT protocol utilizing the binary erasure channel or source. We also propose the bootstrap string OT protocol which provides disjoint (weakened) privacy while achieving a multiplicative increase in rate, thus trading off security for rate. Finally, leveraging our OT protocol, we construct a protocol for SFC and establish a general lower bound on SFC capacity of the binary erasure channel and source.
Beam Selection Gain Versus Antenna Selection Gain
Venue: arXiv cs.IT 2009
Year: 2009

We consider beam selection using a fixed beamforming network (FBN) at a base station with $M$ array antennas. In our setting, a Butler matrix is deployed at the RF stage to form $M$ beams, and then the best beam is selected for transmission. We provide the proofs of the key properties of the noncentral chi-square distribution and the following properties of the beam selection gain verifying that beam selection is superior to antenna selection in Rician channels with any $K$-factors. Furthermore, we find asymptotically tight stochastic bounds of the beam selection gain, which yield approximate closed form expressions of the expected selection gain and the ergodic capacity. Beam selection has the order of growth of the ergodic capacity $\mathnormalΘ(\log(M))$ regardless of user location in contrast to $\mathnormalΘ(\log(\log(M)))$ for antenna selection.
Kolmogorov Complexity and Solovay Functions
Venue: arXiv cs.CC 2009
Year: 2009

Solovay proved that there exists a computable upper bound f of the prefix-free Kolmogorov complexity function K such that f (x) = K(x) for infinitely many x. In this paper, we consider the class of computable functions f such that K(x) <= f (x)+O(1) for all x and f (x) <= K(x) + O(1) for infinitely many x, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-Löf randomness and K-triviality.
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties
Venue: arXiv cs.DS 2009
Year: 2009

We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.
Enumerating Homomorphisms
Venue: arXiv cs.CC 2009
Year: 2009

The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.
An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances
Venue: arXiv cs.DS 2009
Year: 2009

In this paper, we present a factor 16 approximation algorithm for the following NP-hard distance fitting problem: given a finite set X and a distance d on X, find a Robinsonian distance dR on X minimizing the l\infty-error ||d - dR||\infty = maxx,y\epsilonX {|d(x, y) - dR(x, y)|}. A distance dR on a finite set X is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonal along any row or column. Robinsonian distances generalize ultrametrics, line distances and occur in the seriation problems and in classification.
Delay Performance Optimization for Multiuser Diversity Systems with Bursty-Traffic and Heterogeneous Wireless Links
Venue: arXiv cs.IT 2009
Year: 2009

This paper presents a cross-layer approach for optimizing the delay performance of a multiuser diversity system with heterogeneous block-fading channels and a delay-sensitive bursty-traffic. We consider the downlink of a time-slotted multiuser system employing opportunistic scheduling with fair performance at the medium access (MAC) layer and adaptive modulation and coding (AMC) with power control at the physical layer. Assuming individual user buffers which temporarily store the arrival traffic of users at the MAC layer, we first present a large deviations based statistical model to evaluate the delay-bound violation of packets in the user buffers. Aiming at minimizing the delay probability of the individual users, we then optimize the AMC and power control module subject to a target packet-error rate constraint. In the case of a quantized feedback channel, we also present a constant-power AMC based opportunistic scheduling scheme. Numerical and simulation results are provided to evaluate the delay performance of the proposed adaptation schemes in a multiuser setup.
Correlated Sources over Broadcast Channels
Venue: arXiv cs.IT 2009
Year: 2009

The problem of reliable transmission of correlated sources over the broadcast channel, originally studied by Han and Costa, is revisited. An alternative characterization of their sufficient condition for reliable transmission is given, which includes results of Marton for channel coding over broadcast channels and of Gray and Wyner for distributed source coding. A ``minimalistic'' coding scheme is presented, which is based on joint typicality encoding and decoding, without requiring the use of Cover's superposition coding, random hashing, and common part between two sources. The analysis of the coding scheme is also conceptually simple and relies on a new multivariate covering lemma and an application of the Fourier--Motzkin elimination procedure.
An Order on Sets of Tilings Corresponding to an Order on Languages
Venue: arXiv cs.DM 2009
Year: 2009

Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.
Cover Time and Broadcast Time
Venue: arXiv cs.DS 2009
Year: 2009

We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. \cite{CRRST97} that "the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms". In more detail, our results are as follows: For any graph $G=(V,E)$ of size $n$ and minimum degree $δ$, we have $\mathcal{R}(G)= \Oh(\frac{|E|}δ \cdot \log n)$, where $\mathcal{R}(G)$ denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs. For any $δ$-regular (or almost $δ$-regular) graph $G$ it holds that $\mathcal{R}(G) = Ω(\frac{δ^2}{n} \cdot \frac{1}{\log n})$. Together with our upper bound on $\mathcal{R}(G)$, this lower bound strongly confirms the intuition of Chandra et al. for graphs with minimum degree $Θ(n)$, since then the cover time equals the broadcast time multiplied by $n$ (neglecting logarithmic factors). Conversely, for any $δ$ we construct almost $δ$-regular graphs that satisfy $\mathcal{R}(G) = \Oh(\max \{\sqrt{n},δ\} \cdot \log^2 n)$. Since any regular expander satisfies $\mathcal{R}(G) = Θ(n)$, the strong relationship given above does not hold if $δ$ is polynomially smaller than $n$. Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).
On the Dynamics of the Error Floor Behavior in (Regular) LDPC Codes
Venue: arXiv cs.IT 2009
Year: 2009

It is shown that dominant trapping sets of regular LDPC codes, so called absorption sets, undergo a two-phased dynamic behavior in the iterative message-passing decoding algorithm. Using a linear dynamic model for the iteration behavior of these sets, it is shown that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. This analysis is shown to lead to very accurate numerical calculations of the error floor bit error rates down to error rates that are inaccessible by simulation. The topology of the dominant absorption sets of an example code, the IEEE 802.3an (2048,1723) regular LDPC code, are identified and tabulated using topological relationships in combination with search algorithms.
Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots
Venue: arXiv cs.DS 2009
Year: 2009

We consider a team of $k$ identical, oblivious, asynchronous mobile robots that are able to sense (\emph{i.e.}, view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by \emph{deterministic} robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the \emph{exploration} problem of anonymous unoriented rings of any size. It is known that $Θ(\log n)$ robots are necessary and sufficient to solve the problem with $k$ deterministic robots, provided that $k$ and $n$ are coprime. By contrast, we show that \emph{four} identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive.