OpenRaiser/Intern-Atlas huggingface dataset:
Combinatorial Auctions with Restricted Complements
Venue: arXiv cs.GT 2012
Year: 2012

Complements between goods - where one good takes on added value in the presence of another - have been a thorn in the side of algorithmic mechanism designers. On the one hand, complements are common in the standard motivating applications for combinatorial auctions, like spectrum license auctions. On the other, welfare maximization in the presence of complements is notoriously difficult, and this intractability has stymied theoretical progress in the area. For example, there are no known positive results for combinatorial auctions in which bidder valuations are multi-parameter and non-complement-free, other than the relatively weak results known for general valuations. To make inroads on the problem of combinatorial auction design in the presence of complements, we propose a model for valuations with complements that is parameterized by the "size" of the complements. A valuation in our model is represented succinctly by a weighted hypergraph, where the size of the hyper-edges corresponds to degree of complementarity. Our model permits a variety of computationally efficient queries, and non-trivial welfare-maximization algorithms and mechanisms. We design the following polynomial-time approximation algorithms and truthful mechanisms for welfare maximization with bidders with hypergraph valuations. 1- For bidders whose valuations correspond to subgraphs of a known graph that is planar (or more generally, excludes a fixed minor), we give a truthful and (1+epsilon)-approximate mechanism. 2- We give a polynomial-time, r-approximation algorithm for welfare maximization with hypergraph-r valuations. Our algorithm randomly rounds a compact linear programming relaxation of the problem. 3- We design a different approximation algorithm and use it to give a polynomial-time, truthful-in-expectation mechanism that has an approximation factor of O(log^r m).
Guesswork, large deviations and Shannon entropy
Venue: arXiv cs.IT 2012
Year: 2012

How hard is it guess a password? Massey showed that that the Shannon entropy of the distribution from which the password is selected is a lower bound on the expected number of guesses, but one which is not tight in general. In a series of subsequent papers under ever less restrictive stochastic assumptions, an asymptotic relationship as password length grows between scaled moments of the guesswork and specific Rényi entropy was identified. Here we show that, when appropriately scaled, as the password length grows the logarithm of the guesswork satisfies a Large Deviation Principle (LDP), providing direct estimates of the guesswork distribution when passwords are long. The rate function governing the LDP possess a specific, restrictive form that encapsulates underlying structure in the nature of guesswork. Returning to Massey's original observation, a corollary to the LDP shows that expectation of the logarithm of the guesswork is the specific Shannon entropy of the password selection process.
Visualization of features of a series of measurements with one-dimensional cellular structure
Venue: arXiv cs.LG 2012
Year: 2012

This paper describes the method of visualization of periodic constituents and instability areas in series of measurements, being based on the algorithm of smoothing out and concept of one-dimensional cellular automata. A method can be used at the analysis of temporal series, related to the volumes of thematic publications in web-space.
Adaptive Reduced-Rank LCMV Beamforming Algorithms Based on Joint Iterative Optimization of Filters: Design and Analysis
Venue: arXiv cs.OH 2012
Year: 2012

This paper presents reduced-rank linearly constrained minimum variance (LCMV) beamforming algorithms based on joint iterative optimization of filters. The proposed reduced-rank scheme is based on a constrained joint iterative optimization of filters according to the minimum variance criterion. The proposed optimization procedure adjusts the parameters of a projection matrix and an adaptive reducedrank filter that operates at the output of the bank of filters. We describe LCMV expressions for the design of the projection matrix and the reduced-rank filter. We then describe stochastic gradient and develop recursive least-squares adaptive algorithms for their efficient implementation along with automatic rank selection techniques. An analysis of the stability and the convergence properties of the proposed algorithms is presented and semi-analytical expressions are derived for predicting their mean squared error (MSE) performance. Simulations for a beamforming application show that the proposed scheme and algorithms outperform in convergence and tracking the existing full-rank and reduced-rank algorithms while requiring comparable complexity
A Novel Video Compression Approach Based on Underdetermined Blind Source Separation
Venue: arXiv cs.MM 2012
Year: 2012

This paper develops a new video compression approach based on underdetermined blind source separation. Underdetermined blind source separation, which can be used to efficiently enhance the video compression ratio, is combined with various off-the-shelf codecs in this paper. Combining with MPEG-2, video compression ratio could be improved slightly more than 33%. As for combing with H.264, 4X~12X more compression ratio could be achieved with acceptable PSNR, according to different kinds of video sequences.
Parity Check Matrix Recognition from Noisy Codewords
Venue: arXiv cs.IT 2012
Year: 2012

We study recovering parity check relations for an unknown code from intercepted bitstream received from Binary Symmetric Channel in this paper. An iterative column elimination algorithm is introduced which attempts to eliminate parity bits in codewords of noisy data. This algorithm is very practical due to low complexity and use of XOR operator. Since, the computational complexity is low, searching for the length of code and synchronization is possible. Furthermore, the Hamming weight of the parity check words are only used in threshold computation and unlike other algorithms, they have negligible effect in the proposed algorithm. Eventually, experimental results are presented and estimations for the maximum noise level allowed for recovering the words of the parity check matrix are investigated.
Computer Supported Collaborative Processes in Virtual Organizations
Venue: arXiv cs.HC 2012
Year: 2012

In global economy, turbulent organization environment strongly influences organization's operation. Organizations must constantly adapt to changing circumstances and search for new possibilities of gaining competitive advantage. To face this challenge, small organizations base their operation on collaboration within Virtual Organizations (VOs). VO operation is based on collaborative processes. Due to dynamism and required flexibility of collaborative processes, existing business information systems are insufficient to efficiently support them. In this paper a novel method for supporting collaborative processes based on process mining techniques is proposed. The method allows activity patterns in various instances of collaborative processes to be identified and used for recommendation of activities. This provides an opportunity for better computer support of collaborative processes leading to more efficient and effective realization of business goals.
Conditional mean embeddings as regressors - supplementary
Venue: arXiv cs.LG 2012
Year: 2012

We demonstrate an equivalence between reproducing kernel Hilbert space (RKHS) embeddings of conditional distributions and vector-valued regressors. This connection introduces a natural regularized loss function which the RKHS embeddings minimise, providing an intuitive understanding of the embeddings and a justification for their use. Furthermore, the equivalence allows the application of vector-valued regression methods and results to the problem of learning conditional distributions. Using this link we derive a sparse version of the embedding by considering alternative formulations. Further, by applying convergence results for vector-valued regression to the embedding problem we derive minimax convergence rates which are O(\log(n)/n) -- compared to current state of the art rates of O(n^{-1/4}) -- and are valid under milder and more intuitive assumptions. These minimax upper rates coincide with lower rates up to a logarithmic factor, showing that the embedding method achieves nearly optimal rates. We study our sparse embedding algorithm in a reinforcement learning task where the algorithm shows significant improvement in sparsity over an incomplete Cholesky decomposition.
Timing and Code Size Optimization on Achieving Full Parallelism in Uniform Nested Loops
Venue: arXiv cs.PL 2012
Year: 2012

Multidimensional Retiming is one of the most important optimization techniques to improve timing parameters of nested loops. It consists in exploring the iterative and recursive structures of loops to redistribute computation nodes on cycle periods, and thus to achieve full parallelism. However, this technique introduces a large overhead in a loop generation due to the loop transformation. The provided solutions are generally characterized by an important cycle number and a great code size. It represents the most limiting factors while implementing them in embedded systems. In this paper, we present a new Multidimensional Retiming technique, called "Optimal Multidimensional Retiming" (OMDR). It reveals the timing and data dependency characteristics of nodes, to minimize the overhead. The experimental results show that the average improvement on the execution time of the nested loops by our technique is 19.31% compared to the experiments provided by an existent Multidimensional Retiming Technique. The average code size is reduced by 43.53% compared to previous experiments.
Minimum Complexity Pursuit: Stability Analysis
Venue: arXiv cs.IT 2012
Year: 2012

A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist "universal" algorithms for recovering "structured" signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements.
Energy-Efficient Relaying over Multiple Slots with Causal CSI
Venue: arXiv cs.IT 2012
Year: 2012

In many communication scenarios, such as in cellular systems, the energy cost is substantial and should be conserved, yet there is a growing need to support many real-time applications that require timely data delivery. To model such a scenario, in this paper we consider the problem of minimizing the expected sum energy of delivering a message of a given size from a source to a destination subject to a deadline constraint. A relay is present and can assist after it has decoded the message. Causal channel state information (CSI), in the form of present and past SNRs of all links, is available for determining the optimal power allocation for the source and relay. We obtain the optimal power allocation policy by dynamic programming and explore its structure. We also obtain conditions for which the minimum expected sum energy is bounded given a general channel distribution. In particular, we show that for Rayleigh and Rician fading channels, relaying is necessary for the minimum expected sum energy to be bounded. This illustrates the fundamental advantage of relaying from the perspective of energy efficient communications when only causal CSI is available. Numerical results are obtained which show the reduction in the expected sum energy under different communication scenarios.
Bounds on Minimum Number of Anchors for Iterative Localization and its Connections to Bootstrap Percolation
Venue: arXiv cs.IT 2012
Year: 2012

Iterated localization is considered where each node of a network needs to get localized (find its location on 2-D plane), when initially only a subset of nodes have their location information. The iterated localization process proceeds as follows. Starting with a subset of nodes that have their location information, possibly using global positioning system (GPS) devices, any other node gets localized if it has three or more localized nodes in its radio range. The newly localized nodes are included in the subset of nodes that have their location information for the next iteration. This process is allowed to continue, until no new node can be localized. The problem is to find the minimum size of the initially localized subset to start with so that the whole network is localized with high probability. There are intimate connections between iterated localization and bootstrap percolation, that is well studied in statistical physics. Using results known in bootstrap percolation, we find a sufficient condition on the size of the initially localized subset that guarantees the localization of all nodes in the network with high probability.
Detection techniques of selective forwarding attacks in wireless sensor networks: a survey
Venue: arXiv cs.CR 2012
Year: 2012

The wireless sensor network has become a hot research area due its wide range of application in military and civilian domain, but as it uses wireless media for communication these are easily prone to security attacks. There are number of attacks on wireless sensor networks like black hole attack, sink hole attack, Sybil attack, selective forwarding attacks etc. in this paper we will concentrate on selective forwarding attacks In selective forwarding attacks, malicious nodes behave like normal nodes and selectively drop packets. The selection of dropping nodes may be random. Identifying such attacks is very difficult and sometimes impossible. In this paper we have listed up some detection techniques, which have been proposed by different researcher in recent years, there we also have tabular representation of qualitative analysis of detection techniques
Ring Exploration with Oblivious Myopic Robots
Venue: arXiv cs.MA 2012
Year: 2012

The exploration problem in the discrete universe, using identical oblivious asynchronous robots without direct communication, has been well investigated. These robots have sensors that allow them to see their environment and move accordingly. However, the previous work on this problem assume that robots have an unlimited visibility, that is, they can see the position of all the other robots. In this paper, we consider deterministic exploration in an anonymous, unoriented ring using asynchronous, oblivious, and myopic robots. By myopic, we mean that the robots have only a limited visibility. We study the computational limits imposed by such robots and we show that under some conditions the exploration problem can still be solved. We study the cases where the robots visibility is limited to 1, 2, and 3 neighboring nodes, respectively.
Neutron Star Evolutions using Tabulated Equations of State with a New Execution Model
Venue: arXiv cs.DC 2012
Year: 2012

The addition of nuclear and neutrino physics to general relativistic fluid codes allows for a more realistic description of hot nuclear matter in neutron star and black hole systems. This additional microphysics requires that each processor have access to large tables of data, such as equations of state, and in large simulations the memory required to store these tables locally can become excessive unless an alternative execution model is used. In this work we present relativistic fluid evolutions of a neutron star obtained using a message driven multi-threaded execution model known as ParalleX. These neutron star simulations would require substantial memory overhead dedicated entirely to the equation of state table if using a more traditional execution model. We introduce a ParalleX component based on Futures for accessing large tables of data, including out-of-core sized tables, which does not require substantial memory overhead and effectively hides any increased network latency.
The Classification of Complementary Information Set Codes of Lengths 14 and 16
Venue: arXiv cs.IT 2012
Year: 2012

In the paper "A new class of codes for Boolean masking of cryptographic computations," Carlet, Gaborit, Kim, and Solé defined a new class of rate one-half binary codes called \emph{complementary information set} (or CIS) codes. The authors then classified all CIS codes of length less than or equal to 12. CIS codes have relations to classical Coding Theory as they are a generalization of self-dual codes. As stated in the paper, CIS codes also have important practical applications as they may improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we give a complete classification result for length 14 CIS codes using an equivalence relation on $GL(n,\FF_2)$. We also give a new classification for all binary $[16,8,3]$ and $[16,8,4]$ codes. We then complete the classification for length 16 CIS codes and give additional classifications for optimal CIS codes of lengths 20 and 26.
Kinodynamic RRT*: Optimal Motion Planning for Systems with Linear Differential Constraints
Venue: arXiv cs.RO 2012
Year: 2012

We present Kinodynamic RRT*, an incremental sampling-based approach for asymptotically optimal motion planning for robots with linear differential constraints. Our approach extends RRT*, which was introduced for holonomic robots (Karaman et al. 2011), by using a fixed-final-state-free-final-time controller that exactly and optimally connects any pair of states, where the cost function is expressed as a trade-off between the duration of a trajectory and the expended control effort. Our approach generalizes earlier work on extending RRT* to kinodynamic systems, as it guarantees asymptotic optimality for any system with controllable linear dynamics, in state spaces of any dimension. Our approach can be applied to non-linear dynamics as well by using their first-order Taylor approximations. In addition, we show that for the rich subclass of systems with a nilpotent dynamics matrix, closed-form solutions for optimal trajectories can be derived, which keeps the computational overhead of our algorithm compared to traditional RRT* at a minimum. We demonstrate the potential of our approach by computing asymptotically optimal trajectories in three challenging motion planning scenarios: (i) a planar robot with a 4-D state space and double integrator dynamics, (ii) an aerial vehicle with a 10-D state space and linearized quadrotor dynamics, and (iii) a car-like robot with a 5-D state space and non-linear dynamics.
On Burst Error Correction and Storage Security of Noisy Data
Venue: arXiv cs.IT 2012
Year: 2012

Secure storage of noisy data for authentication purposes usually involves the use of error correcting codes. We propose a new model scenario involving burst errors and present for that several constructions.
An Adaptive XP-based approach to Agile Development
Venue: arXiv cs.SE 2012
Year: 2012

Software design is gradually becoming open, distributed, pervasive, and connected. It is a sad statistical fact that software projects are scientifically fragile and tend to fail more than other engineering fields. Agile development is a philosophy. And agile methods are processes that support the agile philosophy. XP places a strong emphasis on technical practices in addition to the more common teamwork and structural practices. In this paper, we elaborate how XP practices can be used to thinking, collaborating, releasing, planning, developing. And the state that make your team and organization more successful.
The Capacity Loss of Dense Constellations
Venue: arXiv cs.IT 2012
Year: 2012

We determine the loss in capacity incurred by using signal constellations with a bounded support over general complex-valued additive-noise channels for suitably high signal-to-noise ratio. Our expression for the capacity loss recovers the power loss of 1.53dB for square signal constellations.
The Finite Field Multi-Way Relay Channel with Correlated Sources: Beyond Three Users
Venue: arXiv cs.IT 2012
Year: 2012

The multi-way relay channel (MWRC) models cooperative communication networks in which many users exchange messages via a relay. In this paper, we consider the finite field MWRC with correlated messages. The problem is to find all achievable rates, defined as the number of channel uses required per reliable exchange of message tuple. For the case of three users, we have previously established that for a special class of source distributions, the set of all achievable rates can be found [Ong et al., ISIT 2010]. The class is specified by an almost balanced conditional mutual information (ABCMI) condition. In this paper, we first generalize the ABCMI condition to the case of more than three users. We then show that if the sources satisfy the ABCMI condition, then the set of all achievable rates is found and can be attained using a separate source-channel coding architecture.
Quantum contextuality in classical information retrieval
Venue: arXiv cs.IR 2012
Year: 2012

Document ranking based on probabilistic evaluations of relevance is known to exhibit non-classical correlations, which may be explained by admitting a complex structure of the event space, namely, by assuming the events to emerge from multiple sample spaces. The structure of event space formed by overlapping sample spaces is known in quantum mechanics, they may exhibit some counter-intuitive features, called quantum contextuality. In this Note I observe that from the structural point of view quantum contextuality looks similar to personalization of information retrieval scenarios. Along these lines, Knowledge Revision is treated as operationalistic measurement and a way to quantify the rate of personalization of Information Retrieval scenarios is suggested.
Measuring the evolution of contemporary western popular music
Venue: arXiv cs.SD 2012
Year: 2012

Popular music is a key cultural expression that has captured listeners' attention for ages. Many of the structural regularities underlying musical discourse are yet to be discovered and, accordingly, their historical evolution remains formally unknown. Here we unveil a number of patterns and metrics characterizing the generic usage of primary musical facets such as pitch, timbre, and loudness in contemporary western popular music. Many of these patterns and metrics have been consistently stable for a period of more than fifty years, thus pointing towards a great degree of conventionalism. Nonetheless, we prove important changes or trends related to the restriction of pitch transitions, the homogenization of the timbral palette, and the growing loudness levels. This suggests that our perception of the new would be rooted on these changing characteristics. Hence, an old tune could perfectly sound novel and fashionable, provided that it consisted of common harmonic progressions, changed the instrumentation, and increased the average loudness.
Tie-RBAC: An application of RBAC to Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

This paper explores the application of role-based access control to social networks, from the perspective of social network analysis. Each tie, composed of a relation, a sender and a receiver, involves the sender's assignation of the receiver to a role with permissions. The model is not constrained to system-defined relations and lets users define them unilaterally. It benefits of RBAC's advantages, such as policy neutrality, simplification of security administration and permissions on other roles. Tie-RBAC has been implemented in a core for building social network sites, Social Stream.