OpenRaiser/Intern-Atlas huggingface dataset:
Equilibrium Pricing of Semantically Substitutable Digital Goods
Venue: arXiv cs.GT 2012
Year: 2012

The problem of arriving at a principled method of pricing goods and services was very satisfactorily solved for conventional goods; however, this solution is not applicable to digital goods. This paper studies pricing of a special class of digital goods, which we call {\em semantically substitutable digital goods}. After taking into consideration idiosyncrasies of goods in this class, we define a market model for it, together with a notion of equilibrium. We prove existence of equilibrium prices for our market model using Kakutani's fixed point theorem. The far reaching significance of a competitive equilibrium is made explicit in the Fundamental Theorems of Welfare Economics. There are basic reasons due to which these theorems are not applicable to digital goods. This naturally leads to the question of whether the allocations of conventional goods are rendered inefficient or "socially unfair" in the mixed economy we have proposed. We prove that that is not the case and that in this sense, the intended goal of Welfare Economics is still achieved in the mixed economy.
The Quantum Query Complexity of AC0
Venue: arXiv cs.CC 2012
Year: 2012

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $Θ(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $Ω(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $Ω((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $Ω(n^{2/3})$ lower bound for the element distinctness problem.
The Approximate Capacity of the Gaussian N-Relay Diamond Network
Venue: arXiv cs.IT 2012
Year: 2012

We consider the Gaussian "diamond" or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N^2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric Gaussian N-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factor O(log^4(N)) of capacity with pre-constant in the order notation independent of the channel gains.
Multiuser broadcast erasure channel with feedback - capacity and algorithms
Venue: arXiv cs.IT 2012
Year: 2012

We consider the $N$-user broadcast erasure channel with $N$ unicast sessions (one for each user) where receiver feedback is regularly sent to the transmitter in the form of ACK/NACK messages. We first provide a generic outer bound to the capacity of this system; we then propose a virtual-queue-based inter-session mixing coding algorithm, determine its rate region and show that it achieves capacity under certain conditions on channel statistics, assuming that instantaneous feedback is known to all users. Removing this assumption results in a rate region that asymptotically differs from the outer bound by 1 bit as $L\to \infty$, where $L$ is the number of bits per packet (packet length). For the case of arbitrary channel statistics, we present a modification of the previous algorithm whose rate region is identical to the outer bound for N=3, when instant feedback is known to all users, and differs from the bound by 1 bit as $L\to \infty$, when the 3 users know only their own ACK. The proposed algorithms do not require any prior knowledge of channel statistics.
The Complexity of Rerouting Shortest Paths
Venue: arXiv cs.CC 2012
Year: 2012

The Shortest Path Reconfiguration problem has as input a graph G (with unit edge lengths) with vertices s and t, and two shortest st-paths P and Q. The question is whether there exists a sequence of shortest st-paths that starts with P and ends with Q, such that subsequent paths differ in only one vertex. This is called a rerouting sequence. This problem is shown to be PSPACE-complete. For claw-free graphs and chordal graphs, it is shown that the problem can be solved in polynomial time, and that shortest rerouting sequences have linear length. For these classes, it is also shown that deciding whether a rerouting sequence exists between all pairs of shortest st-paths can be done in polynomial time. Finally, a polynomial time algorithm for counting the number of isolated paths is given.
Bit-Interleaved Coded Multiple Beamforming with Perfect Coding
Venue: arXiv cs.IT 2012
Year: 2012

When the Channel State Information (CSI) is known by both the transmitter and the receiver, beamforming techniques employing Singular Value Decomposition (SVD) are commonly used in Multiple-Input Multiple-Output (MIMO) systems. Without channel coding, there is a trade-off between full diversity and full multiplexing. When channel coding is added, both of them can be achieved as long as the code rate Rc and the number of employed subchannels S satisfy the condition RcS<=1. By adding a properly designed constellation precoder, both full diversity and full multiplexing can be achieved for both uncoded and coded systems with the trade-off of a higher decoding complexity, e.g., Fully Precoded Multiple Beamforming (FPMB) and Bit-Interleaved Coded Multiple Beamforming with Full Precoding (BICMB-FP) without the condition RcS<=1. Recently discovered Perfect Space-Time Block Code (PSTBC) is a full-rate full-diversity space-time code, which achieves efficient shaping and high coding gain for MIMO systems. In this paper, a new technique, Bit-Interleaved Coded Multiple Beamforming with Perfect Coding (BICMB-PC), is introduced. BICMB-PC transmits PSTBCs through convolutional coded SVD systems. Similar to BICMB-FP, BICMB-PC achieves both full diversity and full multiplexing, and its performance is almost the same as BICMB-FP. The advantage of BICMB-PC is that it can provide a much lower decoding complexity than BICMB-FP, since the real and imaginary parts of the received signal can be separated for BICMB-PC of dimensions 2 and 4, and only the part corresponding to the coded bit is required to acquire one bit metric for the Viterbi decoder.
The surprizing complexity of generalized reachability games
Venue: arXiv cs.CC 2012
Year: 2012

Games on graphs provide a natural and powerful model for reactive systems. In this paper, we consider generalized reachability objectives, defined as conjunctions of reachability objectives. We first prove that deciding the winner in such games is $\PSPACE$-complete, although it is fixed-parameter tractable with the number of reachability objectives as parameter. Moreover, we consider the memory requirements for both players and give matching upper and lower bounds on the size of winning strategies. In order to allow more efficient algorithms, we consider subclasses of generalized reachability games. We show that bounding the size of the reachability sets gives two natural subclasses where deciding the winner can be done efficiently.
Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
Venue: arXiv cs.DM 2012
Year: 2012

An identifying code of a (di)graph $G$ is a dominating subset $C$ of the vertices of $G$ such that all distinct vertices of $G$ have distinct (in)neighbourhoods within $C$. In this paper, we classify all finite digraphs which only admit their whole vertex set in any identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well known theorem of A. Bondy on set systems we classify the extremal cases for this theorem.
Hybrid Linear Modeling via Local Best-fit Flats
Venue: arXiv cs.CV 2012
Year: 2012

We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' $β_2$ numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.
No dimension independent Core-Sets for Containment under Homothetics
Venue: arXiv cs.CG 2012
Year: 2012

This paper deals with the containment problem under homothetics which has the minimal enclosing ball (MEB) problem as a prominent representative. We connect the problem to results in classic convex geometry and introduce a new series of radii, which we call core-radii. For the MEB problem, these radii have already been considered from a different point of view and sharp inequalities between them are known. In this paper sharp inequalities between core-radii for general containment under homothetics are obtained. Moreover, the presented inequalities are used to derive sharp upper bounds on the size of core-sets for containment under homothetics. In the MEB case, this yields a tight (dimension independent) bound for the size of such core-sets. In the general case, we show that there are core-sets of size linear in the dimension and that this bound stays sharp even if the container is required to be symmetric.
Efficient Interpolant Generation in Satisfiability Modulo Linear Integer Arithmetic
Venue: arXiv cs.LO 2012
Year: 2012

The problem of computing Craig interpolants in SAT and SMT has recently received a lot of interest, mainly for its applications in formal verification. Efficient algorithms for interpolant generation have been presented for some theories of interest ---including that of equality and uninterpreted functions, linear arithmetic over the rationals, and their combination--- and they are successfully used within model checking tools. For the theory of linear arithmetic over the integers (LA(Z)), however, the problem of finding an interpolant is more challenging, and the task of developing efficient interpolant generators for the full theory LA(Z) is still the objective of ongoing research. In this paper we try to close this gap. We build on previous work and present a novel interpolation algorithm for SMT(LA(Z)), which exploits the full power of current state-of-the-art SMT(LA(Z)) solvers. We demonstrate the potential of our approach with an extensive experimental evaluation of our implementation of the proposed algorithm in the MathSAT SMT solver.
Normal art galleries: wall in - all in
Venue: arXiv cs.CG 2012
Year: 2012

We introduce the notion of a normal gallery, a gallery in which any configuration of guards that visually covers the walls covers the entire gallery. We show that any star gallery is normal and any gallery with at most two reflex corners is normal. A polynomial time algorithm is provided deciding if, for a given polygon and a finite set of positions, there exists a configuration of guards in some of these positions that visually covers the walls but not the entire gallery.
Random Beamforming over Quasi-Static and Fading Channels: A Deterministic Equivalent Approach
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we study the performance of random isometric precoders over quasi-static and correlated fading channels. We derive deterministic approximations of the mutual information and the signal-to-interference-plus-noise ratio (SINR) at the output of the minimum-mean-square-error (MMSE) receiver and provide simple provably converging fixed-point algorithms for their computation. Although these approximations are only proven exact in the asymptotic regime with infinitely many antennas at the transmitters and receivers, simulations suggest that they closely match the performance of small-dimensional systems. We exemplarily apply our results to the performance analysis of multi-cellular communication systems, multiple-input multiple-output multiple-access channels (MIMO-MAC), and MIMO interference channels. The mathematical analysis is based on the Stieltjes transform method. This enables the derivation of deterministic equivalents of functionals of large-dimensional random matrices. In contrast to previous works, our analysis does not rely on arguments from free probability theory which enables the consideration of random matrix models for which asymptotic freeness does not hold. Thus, the results of this work are also a novel contribution to the field of random matrix theory and applicable to a wide spectrum of practical systems.
Single-Call Mechanisms
Venue: arXiv cs.GT 2012
Year: 2012

Truthfulness is fragile and demanding. It is oftentimes computationally harder than solving the original problem. Even worse, truthfulness can be utterly destroyed by small uncertainties in a mechanism's outcome. One obstacle is that truthful payments depend on outcomes other than the one realized, such as the lengths of non-shortest-paths in a shortest-path auction. Single-call mechanisms are a powerful tool that circumvents this obstacle --- they implicitly charge truthful payments, guaranteeing truthfulness in expectation using only the outcome realized by the mechanism. The cost of such truthfulness is a trade-off between the expected quality of the outcome and the risk of large payments. We largely settle when and to what extent single-call mechanisms are possible. The first single-call construction was discovered by Babaioff, Kleinberg, and Slivkins [BKS10] in single-parameter domains. They give a transformation that turns any monotone, single-parameter allocation rule into a truthful-in-expectation single-call mechanism. Our first result is a natural complement to [BKS10]: we give a new transformation that produces a single-call VCG mechanism from any allocation rule for which VCG payments are truthful. Second, in both the single-parameter and VCG settings, we precisely characterize the possible transformations, showing that that a wide variety of transformations are possible but that all take a very simple form. Finally, we study the inherent trade-off between the expected quality of the outcome and the risk of large payments. We show that our construction and that of [BKS10] simultaneously optimize a variety of metrics in their respective domains. As an example, we analyze pay-per-click advertising auctions, where the truthfulness of the standard VCG-based auction is easily broken when the auctioneer's estimated click-through-rates are imprecise.
Multiple Access Channels with States Causally Known at Transmitters
Venue: arXiv cs.IT 2012
Year: 2012

It has been recently shown by Lapidoth and Steinberg that strictly causal state information can be beneficial in multiple access channels (MACs). Specifically, it was proved that the capacity region of a two-user MAC with independent states, each known strictly causally to one encoder, can be enlarged by letting the encoders send compressed past state information to the decoder. In this work, a generalization of the said strategy is proposed whereby the encoders compress also the past transmitted codewords along with the past state sequences. The proposed scheme uses a combination of long-message encoding, compression of the past state sequences and codewords without binning, and joint decoding over all transmission blocks. The proposed strategy has been recently shown by Lapidoth and Steinberg to strictly improve upon the original one. Capacity results are then derived for a class of channels that include two-user modulo-additive state-dependent MACs. Moreover, the proposed scheme is extended to state-dependent MACs with an arbitrary number of users. Finally, output feedback is introduced and an example is provided to illustrate the interplay between feedback and availability of strictly causal state information in enlarging the capacity region.
Compress-and-Forward Scheme for Relay Networks: Backword Decoding and Connection to Bisubmodular Flows
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a compress-and-forward scheme with backward decoding is presented for the unicast wireless relay network. The encoding at the source and relay is a generalization of the noisy network coding scheme (NNC). While it achieves the same reliable data rate as noisy network coding scheme, the backward decoding allows for a better decoding complexity as compared to the joint decoding of the NNC scheme. Characterizing the layered decoding scheme is shown to be equivalent to characterizing an information flow for the wireless network. A node-flow for a graph with bisubmodular capacity constraints is presented and a max-flow min-cut theorem is proved for it. This generalizes many well-known results of flows over capacity constrained graphs studied in computer science literature. The results for the unicast relay network are generalized to the network with multiple sources with independent messages intended for a single destination.
Power and Delay Aware On-Demand Routing For Ad Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Wide implementation of IEEE 802.11 based networks could lead to deployment of localized wireless data communication environments with a limited number of mobile hosts, called ad hoc networks. Implementation of a proper routing methodology in ad hoc networks makes it efficient in terms of performance. A wide spectrum of routing protocols has been contributed by several researchers. Real time applications have been most popular among the applications, run by ad hoc networks. Such applications strictly adhere to the Quality of Service (QoS) requirements such as overall throughput, end-toend delay and power level. Support of QoS requirements becomes more challenging due to dynamic nature of MANETs, where mobility of nodes results in frequent change in topology. QoS aware routing protocols can serve to the QoS support, which concentrate on determining a path between source and destination with the QoS requirements of the flow being satisfied. We propose a protocol, called Power and Delay aware Temporally Ordered Routing Algorithm (PDTORA), based on Temporally Ordered Routing Algorithm (TORA) Protocol, where verification of power and delay requirements is carried out with a query packet at each node along the path between source and destination. Simulations justify better performance of the proposed new protocol in terms of network lifetime, end-to-end delay and packet delivery ratio as compared to TORA.
Efficient Optimization of Performance Measures by Classifier Adaptation
Venue: arXiv cs.LG 2012
Year: 2012

In practical applications, machine learning algorithms are often needed to learn classifiers that optimize domain specific performance measures. Previously, the research has focused on learning the needed classifier in isolation, yet learning nonlinear classifier for nonlinear and nonsmooth performance measures is still hard. In this paper, rather than learning the needed classifier by optimizing specific performance measure directly, we circumvent this problem by proposing a novel two-step approach called as CAPO, namely to first train nonlinear auxiliary classifiers with existing learning methods, and then to adapt auxiliary classifiers for specific performance measures. In the first step, auxiliary classifiers can be obtained efficiently by taking off-the-shelf learning algorithms. For the second step, we show that the classifier adaptation problem can be reduced to a quadratic program problem, which is similar to linear SVMperf and can be efficiently solved. By exploiting nonlinear auxiliary classifiers, CAPO can generate nonlinear classifier which optimizes a large variety of performance measures including all the performance measure based on the contingency table and AUC, whilst keeping high computational efficiency. Empirical studies show that CAPO is effective and of high computational efficiency, and even it is more efficient than linear SVMperf.
The Complexity of Approximately Counting Stable Roommate Assignments
Venue: arXiv cs.CC 2012
Year: 2012

We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the $k$-attribute model, in which the preference lists are determined by dot products of "preference vectors" with "attribute vectors" and (ii) the $k$-Euclidean model, in which the preference lists are determined by the closeness of the "positions" of the people to their "preferred positions". Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem. We show that counting the number of stable roommate assignments in the $k$-attribute model ($k \geq 4$) and the 3-Euclidean model($k \geq 3$) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) (#IS) in a graph, or counting the number of satisfying assignments of a Boolean formula (#SAT). This means that there can be no FPRAS for any of these problems unless NP=RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments (#SR) unless NP=RP. Utilizing previous results by the authors, we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph (#BIS) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. #BIS is complete with respect to approximation-preserving reductions in the logically-defined complexity class $#RHΠ_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all of $#RHΠ_1$. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.