OpenRaiser/Intern-Atlas huggingface dataset:
Storage Enforcement with Kolmogorov Complexity and List Decoding
Venue: arXiv cs.CC 2011
Year: 2011

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the property that if the server passes the verification with some reasonably high probability then the user can rest assured that the server is storing $x$. In this work we present an optimal solution (in terms of the user's storage and communication) while at the same time ensuring that a server that passes the verification protocol with any reasonable probability will store, to within a small \textit{additive} factor, $C(x)$ bits of information, where $C(x)$ is the plain Kolmogorov complexity of $x$. (Since we cannot prevent the server from compressing $x$, $C(x)$ is a natural upper bound.) The proof of security of our protocol combines Kolmogorov complexity with list decoding and unlike previous work that relies upon cryptographic assumptions, we allow the server to have unlimited computational power. To the best of our knowledge, this is the first work that combines Kolmogorov complexity and list decoding. Our framework is general enough to capture extensions where the user splits up $x$ and stores the fragment across multiple servers and our verification protocol can handle non-responsive servers and colluding servers. As a by-product, we also get a proof of retrievability. Finally, our results also have an application in `storage enforcement' schemes, which in turn have an application in trying to update a remote server that is potentially infected with a virus.
Pushing undecidability of the isolation problem for probabilistic automata
Venue: arXiv cs.FL 2011
Year: 2011

This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition.
Problems parameterized by treewidth tractable in single exponential time: a logical approach
Venue: arXiv cs.DS 2011
Year: 2011

We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time when parameterized by treewidth. It appears that all these results can be subsumed by the theorem that model checking of ECML admits an algorithm with such complexity. We extend ECML by adding connectivity requirements and, using the Cut&Count technique introduced by Cygan et al. [4], prove that problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigationality of the introduced logic is justified by a negative result that two expository problems involving non-acyclic conditions, C_l VERTEX DELETION and GIRTH>l VERTEX DELETION for l>=5, do not admit such a robust algorithm unless Exponential Time Hypothesis fails.
Dynamic Packet Scheduler Optimization in Wireless Relay Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this work, we investigate the optimal dynamic packet scheduling policy in a wireless relay network (WRN). We model this network by two sets of parallel queues, that represent the subscriber stations (SS) and the relay stations (RS), with random link connectivity. An optimal policy minimizes, in stochastic ordering sense, the process of cost function of the SS and RS queue sizes. We prove that, in a system with symmetrical connectivity and arrival distributions, a policy that tries to balance the lengths of all the system queues, at every time slot, is optimal. We use stochastic dominance and coupling arguments in our proof. We also provide a low-overhead algorithm for optimal policy implementation.
The Two Bicliques Problem is in NP intersection coNP
Venue: arXiv cs.CC 2011
Year: 2011

We show that the problem of deciding whether the vertex set of a graph can be covered with at most two bicliques is in NP$\cap$coNP. We thus almost determine the computational complexity of a problem whose status has remained open for quite some time. Our result implies that a polynomial time algorithm for the problem is more likely than it being NP-complete unless P = NP.
Least-squares based iterative multipath super-resolution technique
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the problem of multipath channel estimation for direct sequence spread spectrum signals. To resolve multipath components arriving within a short interval, we propose a new algorithm called the least-squares based iterative multipath super-resolution (LIMS). Compared to conventional super-resolution techniques, such as the multiple signal classification (MUSIC) and the estimation of signal parameters via rotation invariance techniques (ESPRIT), our algorithm has several appealing features. In particular, even in critical situations where the conventional super-resolution techniques are not very powerful due to limited data or the correlation between path coefficients, the LIMS algorithm can produce successful results. In addition, due to its iterative nature, the LIMS algorithm is suitable for recursive multipath tracking, whereas the conventional super-resolution techniques may not be. Through numerical simulations, we show that the LIMS algorithm can resolve the first arrival path among closely arriving independently faded multipaths with a much lower mean square error than can conventional early-late discriminator based techniques.
Extended force density method and its expressions
Venue: arXiv cs.CE 2011
Year: 2011

The objective of this work can be divided into two parts. The first one is to propose an extension of the force density method (FDM)(H.J. Schek, 1974), a form-finding method for prestressed cable-net structures. The second one is to present a review of various form-finding methods for tension structures, in the relation with the extended FDM. In the first part, it is pointed out that the original FDM become useless when it is applied to the prestressed structures that consist of combinations of both tension and compression members, while the FDM is usually advantageous in form-finding analysis of cable-nets. To eliminate the limitation, a functional whose stationary problem simply represents the FDM is firstly proposed. Additionally, the existence of a variational principle in the FDM is also indicated. Then, the FDM is extensively redefined by generalizing the formulation of the functional. As the result, the generalized functionals enable us to find the forms of tension structures that consist of combinations of both tension and compression members, such as tensegrities and suspended membranes with compression struts. In the second part, it is indicated the important role of three expressions used by the description of the extended FDM, such as stationary problems of functionals, the principle of virtual work and stationary conditions using Nabla symbol. They can be commonly found in general problems of statics, whereas the original FDM only provides a particular form of equilibrium equation. Then, to demonstrate the advantage of such expressions, various form-finding methods are reviewed and compared. As the result, the common features and the differences over various form-finding methods are examined. Finally, to give an overview of the reviewed methods, the corresponding expressions are shown in the form of three tables.
Directed Nowhere Dense Classes of Graphs
Venue: arXiv cs.DM 2011
Year: 2011

We introduce the concept of shallow directed minors and based on this a new classification of classes of directed graphs which is diametric to existing directed graph decompositions and width measures proposed in the literature. We then study in depth one type of classes of directed graphs which we call nowhere crownful. The classes are very general as they include, on one hand, all classes of directed graphs whose underlying undirected class is nowhere dense, such as planar, bounded-genus, and $H$-minor-free graphs; and on the other hand, also contain classes of high edge density whose underlying class is not nowhere dense. Yet we are able to show that problems such as directed dominating set and many others become fixed-parameter tractable on nowhere crownful classes of directed graphs. This is of particular interest as these problems are not tractable on any existing digraph measure for sparse classes. The algorithmic results are established via proving a structural equivalence of nowhere crownful classes and classes of graphs which are directed uniformly quasi-wide. This rather surprising result is inspired by Nesetril and Ossana de Mendez (2008) and yet a different and more delicate proof is needed, which is a significant part of our contribution.
An expert system for detecting automobile insurance fraud using social network analysis
Venue: arXiv cs.AI 2011
Year: 2011

The article proposes an expert system for detection, and subsequent investigation, of groups of collaborating automobile insurance fraudsters. The system is described and examined in great detail, several technical difficulties in detecting fraud are also considered, for it to be applicable in practice. Opposed to many other approaches, the system uses networks for representation of data. Networks are the most natural representation of such a relational domain, allowing formulation and analysis of complex relations between entities. Fraudulent entities are found by employing a novel assessment algorithm, \textit{Iterative Assessment Algorithm} (\textit{IAA}), also presented in the article. Besides intrinsic attributes of entities, the algorithm explores also the relations between entities. The prototype was evaluated and rigorously analyzed on real world data. Results show that automobile insurance fraud can be efficiently detected with the proposed system and that appropriate data representation is vital.
Fairness Through Awareness
Venue: arXiv cs.CC 2011
Year: 2011

We study fairness in classification, where individuals are classified, e.g., admitted to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, while maintaining utility for the classifier (the university). The main conceptual contribution of this paper is a framework for fair classification comprising (1) a (hypothetical) task-specific metric for determining the degree to which individuals are similar with respect to the classification task at hand; (2) an algorithm for maximizing utility subject to the fairness constraint, that similar individuals are treated similarly. We also present an adaptation of our approach to achieve the complementary goal of "fair affirmative action," which guarantees statistical parity (i.e., the demographics of the set of individuals receiving any classification are the same as the demographics of the underlying population), while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: when fairness implies privacy, and how tools developed in the context of differential privacy may be applied to fairness.
Improving digital signal interpolation: L2-optimal kernels with kernel-invariant interpolation speed
Venue: arXiv cs.CV 2011
Year: 2011

Interpolation is responsible for digital signal resampling and can significantly degrade the original signal quality if not done properly. For many years, optimal interpolation algorithms were sought within constrained classes of interpolation kernel functions. We derive a new family of unconstrained L2-optimal interpolation kernels, and compare their properties to the previously known. Although digital images are used to illustrate this work, our L2-optimal kernels can be applied to interpolate any digital signals.
Seeking Meaning in a Space Made out of Strokes, Radicals, Characters and Compounds
Venue: arXiv cs.CL 2011
Year: 2011

Chinese characters can be compared to a molecular structure: a character is analogous to a molecule, radicals are like atoms, calligraphic strokes correspond to elementary particles, and when characters form compounds, they are like molecular structures. In chemistry the conjunction of all of these structural levels produces what we perceive as matter. In language, the conjunction of strokes, radicals, characters, and compounds produces meaning. But when does meaning arise? We all know that radicals are, in some sense, the basic semantic components of Chinese script, but what about strokes? Considering the fact that many characters are made by adding individual strokes to (combinations of) radicals, we can legitimately ask the question whether strokes carry meaning, or not. In this talk I will present my project of extending traditional NLP techniques to radicals and strokes, aiming to obtain a deeper understanding of the way ideographic languages model the world.
Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing
Venue: arXiv cs.IT 2011
Year: 2011

We demonstrate that sub-wavelength optical images borne on partially-spatially-incoherent light can be recovered, from their far-field or from the blurred image, given the prior knowledge that the image is sparse, and only that. The reconstruction method relies on the recently demonstrated sparsity-based sub-wavelength imaging. However, for partially-spatially-incoherent light, the relation between the measurements and the image is quadratic, yielding non-convex measurement equations that do not conform to previously used techniques. Consequently, we demonstrate new algorithmic methodology, referred to as quadratic compressed sensing, which can be applied to a range of other problems involving information recovery from partial correlation measurements, including when the correlation function has local dependencies. Specifically for microscopy, this method can be readily extended to white light microscopes with the additional knowledge of the light source spectrum.
Enforcing efficient equilibria in network design games via subsidies
Venue: arXiv cs.GT 2011
Year: 2011

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users' selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results.
Aperiodic logarithmic signatures
Venue: arXiv cs.CR 2011
Year: 2011

In this paper we propose a method to construct logarithmic signatures which are not amalgamated transversal and further do not even have a periodic block. The latter property was crucial for the successful attack on the system MST3 by Blackburn et al. [1]. The idea for our construction is based on the theory in Szabó's book about group factorizations [12].
Determining L(2,1)-Span in Polynomial Space
Venue: arXiv cs.DM 2011
Year: 2011

A $k$-L(2,1)-labeling of a graph is a function from its vertex set into the set $\{0,...,k\}$, such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. It is known that finding the smallest $k$ admitting the existence of a $k$-L(2,1)-labeling of any given graph is NP-Complete. In this paper we present an algorithm for this problem, which works in time $O(\complexity ^n)$ and polynomial memory, where $\eps$ is an arbitrarily small positive constant. This is the first exact algorithm for L(2,1)-labeling problem with time complexity $O(c^n)$ for some constant $c$ and polynomial space complexity.
A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction
Venue: arXiv cs.SY 2011
Year: 2011

With increasing use of digital control it is natural to view control inputs and outputs as stochastic processes assuming values over finite alphabets rather than in a Euclidean space. As control over networks becomes increasingly common, data compression by reducing the size of the input and output alphabets without losing the fidelity of representation becomes relevant. This requires us to define a notion of distance between two stochastic processes assuming values in distinct sets, possibly of different cardinalities. If the two processes are i.i.d., then the problem becomes one of defining a metric between two probability distributions over distinct finite sets of possibly different cardinalities. This is the problem addressed in the present paper. A metric is defined in terms of a joint distribution on the product of the two sets, which has the two given distributions as its marginals, and has minimum entropy. Computing the metric exactly turns out to be NP-hard. Therefore an efficient greedy algorithm is presented for finding an upper bound on the distance. This problem also turns out to be NP-hard, so again a greedy algorithm is constructed for finding a suboptimal reduced order approximation. Taken together, all the results presented here permit the approximation of an i.i.d. process over a set of large cardinality by another i.i.d. process over a set of smaller cardinality. In future work, attempts will be made to extend this work to Markov processes over finite sets.
ChemXSeer Digital Library Gaussian Search
Venue: arXiv cs.DL 2011
Year: 2011

We report on the Gaussian file search system designed as part of the ChemXSeer digital library. Gaussian files are produced by the Gaussian software [4], a software package used for calculating molecular electronic structure and properties. The output files are semi-structured, allowing relatively easy access to the Gaussian attributes and metadata. Our system is currently capable of searching Gaussian documents using a boolean combination of atoms (chemical elements) and attributes. We have also implemented a faceted browsing feature on three important Gaussian attribute types - Basis Set, Job Type and Method Used. The faceted browsing feature enables a user to view and process a smaller, filtered subset of documents.
Tree-Structured Random Vector Quantization for Limited-Feedback Wireless Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider the quantization of a transmit beamforming vector in multiantenna channels and of a signature vector in code division multiple access (CDMA) systems. Assuming perfect channel knowledge, the receiver selects for a transmitter the vector that maximizes the performance from a random vector quantization (RVQ) codebook, which consists of independent isotropically distributed unit-norm vectors. The quantized vector is then relayed to the transmitter via a rate-limited feedback channel. The RVQ codebook requires an exhaustive search to locate the selected entry. To reduce the search complexity, we apply generalized Lloyd or $k$-dimensional (kd)-tree algorithms to organize RVQ entries into a tree. In examples shown, the search complexity of tree-structured (TS) RVQ can be a few orders of magnitude less than that of the unstructured RVQ for the same performance. We also derive the performance approximation for TS-RVQ in a large system limit, which predicts the performance of a moderate-size system very well.
Local Optimality Certificates for LP Decoding of Tanner Codes
Venue: arXiv cs.IT 2011
Year: 2011

We present a new combinatorial characterization for local optimality of a codeword in an irregular Tanner code. The main novelty in this characterization is that it is based on a linear combination of subtrees in the computation trees. These subtrees may have any degree in the local code nodes and may have any height (even greater than the girth). We expect this new characterization to lead to improvements in bounds for successful decoding. We prove that local optimality in this new characterization implies ML-optimality and LP-optimality, as one would expect. Finally, we show that is possible to compute efficiently a certificate for the local optimality of a codeword given an LLR vector.
MGA trajectory planning with an ACO-inspired algorithm
Venue: arXiv cs.CE 2011
Year: 2011

Given a set of celestial bodies, the problem of finding an optimal sequence of swing-bys, deep space manoeuvres (DSM) and transfer arcs connecting the elements of the set is combinatorial in nature. The number of possible paths grows exponentially with the number of celestial bodies. Therefore, the design of an optimal multiple gravity assist (MGA) trajectory is a NP-hard mixed combinatorial-continuous problem. Its automated solution would greatly improve the design of future space missions, allowing the assessment of a large number of alternative mission options in a short time. This work proposes to formulate the complete automated design of a multiple gravity assist trajectory as an autonomous planning and scheduling problem. The resulting scheduled plan will provide the optimal planetary sequence and a good estimation of the set of associated optimal trajectories. The trajectory model consists of a sequence of celestial bodies connected by twodimensional transfer arcs containing one DSM. For each transfer arc, the position of the planet and the spacecraft, at the time of arrival, are matched by varying the pericentre of the preceding swing-by, or the magnitude of the launch excess velocity, for the first arc. For each departure date, this model generates a full tree of possible transfers from the departure to the destination planet. Each leaf of the tree represents a planetary encounter and a possible way to reach that planet. An algorithm inspired by Ant Colony Optimization (ACO) is devised to explore the space of possible plans. The ants explore the tree from departure to destination adding one node at the time: every time an ant is at a node, a probability function is used to select a feasible direction. This approach to automatic trajectory planning is applied to the design of optimal transfers to Saturn and among the Galilean moons of Jupiter.