OpenRaiser/Intern-Atlas huggingface dataset:
On the hardness of the noncommutative determinant
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below: 1. We show that if the noncommutative determinant polynomial has small noncommutative arithmetic circuits then so does the noncommutative permanent. Consequently, the commutative permanent polynomial has small commutative arithmetic circuits. 2. For any field F we show that computing the n X n permanent over F is polynomial-time reducible to computing the 2n X 2n (noncommutative) determinant whose entries are O(n^2) X O(n^2) matrices over the field F. 3. We also derive as a consequence that computing the n X n permanent over nonnegative rationals is polynomial-time reducible to computing the noncommutative determinant over Clifford algebras of n^{O(1)} dimension. Our techniques are elementary and use primarily the notion of the Hadamard Product of noncommutative polynomials.
A Construction of Systematic MDS Codes with Minimum Repair Bandwidth
Venue: arXiv cs.IT 2009
Year: 2009

In a distributed storage system based on erasure coding, an important problem is the \emph{repair problem}: If a node storing a coded piece fails, in order to maintain the same level of reliability, we need to create a new encoded piece and store it at a new node. This paper presents a construction of systematic $(n,k)$-MDS codes for $2k\le n$ that achieves the minimum repair bandwidth when repairing from $k+1$ nodes.
Interference Channels with Strong Secrecy
Venue: arXiv cs.IT 2009
Year: 2009

It is known that given the real sum of two independent uniformly distributed lattice points from the same nested lattice codebook, the eavesdropper can obtain at most 1 bit of information per channel regarding the value of one of the lattice points. In this work, we study the effect of this 1 bit information on the equivocation expressed in three commonly used information theoretic measures, i.e., the Shannon entropy, the Renyi entropy and the min entropy. We then demonstrate its applications in an interference channel with a confidential message. In our previous work, we showed that nested lattice codes can outperform Gaussian codes for this channel when the achieved rate is measured with the weak secrecy notion. Here, with the Renyi entropy and the min entropy measure, we prove that the same secure degree of freedom is achievable with the strong secrecy notion as well. A major benefit of the new coding scheme is that the strong secrecy is generated from a single lattice point instead of a sequence of lattice points. Hence the mutual information between the confidential message and the observation of the eavesdropper decreases much faster with the number of channel uses than previously known strong secrecy coding methods for nested lattice codes.
Scalable Distributed-Memory External Sorting
Venue: arXiv cs.DS 2009
Year: 2009

We engineer algorithms for sorting huge data sets on massively parallel machines. The algorithms are based on the multiway merging paradigm. We first outline an algorithm whose I/O requirement is close to a lower bound. Thus, in contrast to naive implementations of multiway merging and all other approaches known to us, the algorithm works with just two passes over the data even for the largest conceivable inputs. A second algorithm reduces communication overhead and uses more conventional specifications of the result at the cost of slightly increased I/O requirements. An implementation wins the well known sorting benchmark in several categories and by a large margin over its competitors.
DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements
Venue: arXiv cs.DC 2009
Year: 2009

In this correspondence, we present an algorithm for distributed sensor localization with noisy distance measurements (DILAND) that extends and makes the DLRE more robust. DLRE is a distributed sensor localization algorithm in $\mathbb{R}^m$ $(m\geq1)$ introduced in \cite{usman_loctsp:08}. DILAND operates when (i) the communication among the sensors is noisy; (ii) the communication links in the network may fail with a non-zero probability; and (iii) the measurements performed to compute distances among the sensors are corrupted with noise. The sensors (which do not know their locations) lie in the convex hull of at least $m+1$ anchors (nodes that know their own locations.) Under minimal assumptions on the connectivity and triangulation of each sensor in the network, this correspondence shows that, under the broad random phenomena described above, DILAND converges almost surely (a.s.) to the exact sensor locations.
An Evolutionary Squeaky Wheel Optimisation Approach to Personnel Scheduling
Venue: arXiv cs.AI 2009
Year: 2009

The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyse a technique called Evolutionary Squeaky Wheel Optimisation and apply it to two different personnel scheduling problems. Evolutionary Squeaky Wheel Optimisation improves the original Squeaky Wheel Optimisation's effectiveness and execution speed by incorporating two extra steps (Selection and Mutation) for added evolution. In the Evolutionary Squeaky Wheel Optimisation, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The aim of the Analysis step is to identify below average solution components by calculating a fitness value for all components. The Selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The Mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repairs are carried out by using the Prioritization to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, improvement in the Evolutionary Squeaky Wheel Optimisation is achieved by selective solution disruption mixed with interative improvement and constructive repair. Strong experimental results are reported on two different domains of personnel scheduling: bus and rail driver scheduling and hospital nurse scheduling.
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
Venue: arXiv cs.DM 2009
Year: 2009

In the context of proving lower bounds on proof space in k-DNF resolution, [Ben-Sasson and Nordstrom 2009] introduced the concept of minimally unsatisfiable sets of k-DNF formulas and proved that a minimally unsatisfiable k-DNF set with m formulas can have at most O((mk)^(k+1)) variables. They also gave an example of such sets with Omega(mk^2) variables. In this paper we significantly improve the lower bound to Omega(m)^k, which almost matches the upper bound above. Furthermore, we show that this implies that the analysis of their technique for proving time-space separations and trade-offs for k-DNF resolution is almost tight. This means that although it is possible, or even plausible, that stronger results than in [Ben-Sasson and Nordstrom 2009] should hold, a fundamentally different approach would be needed to obtain such results.
Iterators, Recursors and Interaction Nets
Venue: arXiv cs.PL 2009
Year: 2009

We propose a method for encoding iterators (and recursion operators in general) using interaction nets (INs). There are two main applications for this: the method can be used to obtain a visual nota- tion for functional programs; and it can be used to extend the existing translations of the lambda-calculus into INs to languages with recursive types.
On the Delay of Network Coding over Line Networks
Venue: arXiv cs.IT 2009
Year: 2009

We analyze a simple network where a source and a receiver are connected by a line of erasure channels of different reliabilities. Recent prior work has shown that random linear network coding can achieve the min-cut capacity and therefore the asymptotic rate is determined by the worst link of the line network. In this paper we investigate the delay for transmitting a batch of packets, which is a function of all the erasure probabilities and the number of packets in the batch. We show a monotonicity result on the delay function and derive simple expressions which characterize the expected delay behavior of line networks. Further, we use a martingale bounded differences argument to show that the actual delay is tightly concentrated around its expectation.
VRAC: Simulation Results #1
Venue: arXiv cs.NI 2009
Year: 2009

In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks are dependent either on expensive and sometimes unavailable hardware (e.g. GPS) or on sophisticated localization calculus (e.g. triangulation) which are both error-prone and with a costly overhead. Instead of localizing nodes in a traditional 2-dimensional space, we use directly the raw distance to a set of anchors to route messages in a multi-dimensional space. This should enable us to use any geographic routing protocol in a robust and efficient manner in a very large range of scenarios. We test this technique for two different geographic routing algorithms, namely GRIC and ROAM. The simulation results show that using the raw coordinates does not decrease their efficiency.
On the Achievable Throughput Region of Multiple-Access Fading Channels with QoS Constraints
Venue: arXiv cs.IT 2009
Year: 2009

Effective capacity, which provides the maximum constant arrival rate that a given service process can support while satisfying statistical delay constraints, is analyzed in a multiuser scenario. In particular, we study the achievable effective capacity region of the users in multiaccess fading channels (MAC) in the presence of quality of service (QoS) constraints. We assume that channel side information (CSI) is available at both the transmitters and the receiver, and superposition coding technique with successive decoding is used. When the power is fixed at the transmitters, we show that varying the decoding order with respect to the channel state can significantly increase the achievable throughput region. For a two-user case, we obtain the optimal decoding strategy when the users have the same QoS constraints. Meanwhile, it is shown that time-division multiple-access (TDMA) can achieve better performance than superposition coding with fixed successive decoding order at the receiver side for certain QoS constraints. For power and rate adaptation, we determine the optimal power allocation policy with fixed decoding order at the receiver side. Numerical results are provided to demonstrate our results.
A History of Until
Venue: arXiv cs.LO 2009
Year: 2009

Until is a notoriously difficult temporal operator as it is both existential and universal at the same time: A until B holds at the current time instant w iff either B holds at w or there exists a time instant w' in the future at which B holds and such that A holds in all the time instants between the current one and w'. This "ambivalent" nature poses a significant challenge when attempting to give deduction rules for until. In this paper, in contrast, we make explicit this duality of until to provide well-behaved natural deduction rules for linear-time logics by introducing a new temporal operator that allows us to formalize the "history" of until, i.e., the "internal" universal quantification over the time instants between the current one and w'. This approach provides the basis for formalizing deduction systems for temporal logics endowed with the until operator. For concreteness, we give here a labeled natural deduction system for a linear-time logic endowed with the new operator and show that, via a proper translation, such a system is also sound and complete with respect to the linear temporal logic LTL with until.
ScotGrid: Providing an Effective Distributed Tier-2 in the LHC Era
Venue: arXiv cs.DC 2009
Year: 2009

ScotGrid is a distributed Tier-2 centre in the UK with sites in Durham, Edinburgh and Glasgow. ScotGrid has undergone a huge expansion in hardware in anticipation of the LHC and now provides more than 4MSI2K and 500TB to the LHC VOs. Scaling up to this level of provision has brought many challenges to the Tier-2 and we show in this paper how we have adopted new methods of organising the centres, from fabric management and monitoring to remote management of sites to management and operational procedures, to meet these challenges. We describe how we have coped with different operational models at the sites, where Glagsow and Durham sites are managed "in house" but resources at Edinburgh are managed as a central university resource. This required the adoption of a different fabric management model at Edinburgh and a special engagement with the cluster managers. Challenges arose from the different job models of local and grid submission that required special attention to resolve. We show how ScotGrid has successfully provided an infrastructure for ATLAS and LHCb Monte Carlo production. Special attention has been paid to ensuring that user analysis functions efficiently, which has required optimisation of local storage and networking to cope with the demands of user analysis. Finally, although these Tier-2 resources are pledged to the whole VO, we have established close links with our local physics user communities as being the best way to ensure that the Tier-2 functions effectively as a part of the LHC grid computing framework..
Fading Cognitive Multiple-Access Channels With Confidential Messages
Venue: arXiv cs.IT 2009
Year: 2009

The fading cognitive multiple-access channel with confidential messages (CMAC-CM) is investigated, in which two users attempt to transmit common information to a destination and user 1 also has confidential information intended for the destination. User 1 views user 2 as an eavesdropper and wishes to keep its confidential information as secret as possible from user 2. The multiple-access channel (both the user-to-user channel and the user-to-destination channel) is corrupted by multiplicative fading gain coefficients in addition to additive white Gaussian noise. The channel state information (CSI) is assumed to be known at both the users and the destination. A parallel CMAC-CM with independent subchannels is first studied. The secrecy capacity region of the parallel CMAC-CM is established, which yields the secrecy capacity region of the parallel CMAC-CM with degraded subchannels. Next, the secrecy capacity region is established for the parallel Gaussian CMAC-CM, which is used to study the fading CMAC-CM. When both users know the CSI, they can dynamically change their transmission powers with the channel realization to achieve the optimal performance. The closed-form power allocation function that achieves every boundary point of the secrecy capacity region is derived.
Self-concordant analysis for logistic regression
Venue: arXiv cs.LG 2009
Year: 2009

Most of the non-asymptotic theoretical work in regression is carried out for the square loss, where estimators can be obtained through closed-form expressions. In this paper, we use and extend tools from the convex optimization literature, namely self-concordant functions, to provide simple extensions of theoretical results for the square loss to the logistic loss. We apply the extension techniques to logistic regression with regularization by the $\ell_2$-norm and regularization by the $\ell_1$-norm, showing that new results for binary classification through logistic regression can be easily derived from corresponding results for least-squares regression.
Sum of Us: Strategyproof Selection from the Selectors
Venue: arXiv cs.GT 2009
Year: 2009

We consider directed graphs over a set of n agents, where an edge (i,j) is taken to mean that agent i supports or trusts agent j. Given such a graph and an integer k\leq n, we wish to select a subset of k agents that maximizes the sum of indegrees, i.e., a subset of k most popular or most trusted agents. At the same time we assume that each individual agent is only interested in being selected, and may misreport its outgoing edges to this end. This problem formulation captures realistic scenarios where agents choose among themselves, which can be found in the context of Internet search, social networks like Twitter, or reputation systems like Epinions. Our goal is to design mechanisms without payments that map each graph to a k-subset of agents to be selected and satisfy the following two constraints: strategyproofness, i.e., agents cannot benefit from misreporting their outgoing edges, and approximate optimality, i.e., the sum of indegrees of the selected subset of agents is always close to optimal. Our first main result is a surprising impossibility: for k \in {1,...,n-1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. Our second main result is a randomized strategyproof mechanism with an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.
Parallelization of the LBG Vector Quantization Algorithm for Shared Memory Systems
Venue: arXiv cs.CV 2009
Year: 2009

This paper proposes a parallel approach for the Vector Quantization (VQ) problem in image processing. VQ deals with codebook generation from the input training data set and replacement of any arbitrary data with the nearest codevector. Most of the efforts in VQ have been directed towards designing parallel search algorithms for the codebook, and little has hitherto been done in evolving a parallelized procedure to obtain an optimum codebook. This parallel algorithm addresses the problem of designing an optimum codebook using the traditional LBG type of vector quantization algorithm for shared memory systems and for the efficient usage of parallel processors. Using the codebook formed from a training set, any arbitrary input data is replaced with the nearest codevector from the codebook. The effectiveness of the proposed algorithm is indicated.
A $p$-adic RanSaC algorithm for stereo vision using Hensel lifting
Venue: arXiv cs.CV 2009
Year: 2009

A $p$-adic variation of the Ran(dom) Sa(mple) C(onsensus) method for solving the relative pose problem in stereo vision is developped. From two 2-adically encoded images a random sample of five pairs of corresponding points is taken, and the equations for the essential matrix are solved by lifting solutions modulo 2 to the 2-adic integers. A recently devised $p$-adic hierarchical classification algorithm imitating the known LBG quantisation method classifies the solutions for all the samples after having determined the number of clusters using the known intra-inter validity of clusterings. In the successful case, a cluster ranking will determine the cluster containing a 2-adic approximation to the "true" solution of the problem.
Multi-core architectures: Complexities of performance prediction and the impact of cache topology
Venue: arXiv cs.PF 2009
Year: 2009

The balance metric is a simple approach to estimate the performance of bandwidth-limited loop kernels. However, applying the method to in-cache situations and modern multi-core architectures yields unsatisfactory results. This paper analyzes the in uence of cache hierarchy design on performance predictions for bandwidth-limited loop kernels on current mainstream processors. We present a diagnostic model with improved predictive power, correcting the limitations of the simple balance metric. The importance of code execution overhead even in bandwidth-bound situations is emphasized. Finally we analyze the impact of synchronization overhead on multi-threaded performance with a special emphasis on the in uence of cache topology.
On the Structure of Real-Time Encoders and Decoders in a Multi-Terminal Communication System
Venue: arXiv cs.IT 2009
Year: 2009

A real-time communication system with two encoders communicating with a single receiver over separate noisy channels is considered. The two encoders make distinct partial observations of a Markov source. Each encoder must encode its observations into a sequence of discrete symbols. The symbols are transmitted over noisy channels to a finite memory receiver that attempts to reconstruct some function of the state of the Markov source. Encoding and decoding must be done in real-time, that is, the distortion measure does not tolerate delays. Under the assumption that the encoders' observations are conditionally independent Markov chains given an unobserved time-invariant random variable, results on the structure of optimal real-time encoders and the receiver are obtained. It is shown that there exist finite-dimensional sufficient statistics for the encoders. The problem with noiseless channels and perfect memory at the receiver is then considered. A new methodology to find the structure of optimal real-time encoders is employed. A sufficient statistic with a time-invariant domain is found for this problem. This methodology exploits the presence of common information between the encoders and the receiver when communication is over noiseless channels.
Error-correcting codes and phase transitions
Venue: arXiv cs.IT 2009
Year: 2009

The theory of error-correcting codes is concerned with constructing codes that optimize simultaneously transmission rate and relative minimum distance. These conflicting requirements determine an asymptotic bound, which is a continuous curve in the space of parameters. The main goal of this paper is to relate the asymptotic bound to phase diagrams of quantum statistical mechanical systems. We first identify the code parameters with Hausdorff and von Neumann dimensions, by considering fractals consisting of infinite sequences of code words. We then construct operator algebras associated to individual codes. These are Toeplitz algebras with a time evolution for which the KMS state at critical temperature gives the Hausdorff measure on the corresponding fractal. We extend this construction to algebras associated to limit points of codes, with non-uniform multi-fractal measures, and to tensor products over varying parameters.
A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
Venue: arXiv cs.NA 2009
Year: 2009

We consider the problem of reconstructing a low-rank matrix from a small subset of its entries. In this paper, we describe the implementation of an efficient algorithm called OptSpace, based on singular value decomposition followed by local manifold optimization, for solving the low-rank matrix completion problem. It has been shown that if the number of revealed entries is large enough, the output of singular value decomposition gives a good estimate for the original matrix, so that local optimization reconstructs the correct matrix with high probability. We present numerical results which show that this algorithm can reconstruct the low rank matrix exactly from a very small subset of its entries. We further study the robustness of the algorithm with respect to noise, and its performance on actual collaborative filtering datasets.