OpenRaiser/Intern-Atlas huggingface dataset:
Almost-natural proofs
Venue: arXiv cs.CC 2009
Year: 2009

Razborov and Rudich have shown that so-called "natural proofs" are not useful for separating P from NP unless hard pseudorandom number generators do not exist. This famous result is widely regarded as a serious barrier to proving strong lower bounds in circuit complexity theory. By definition, a natural combinatorial property satisfies two conditions, constructivity and largeness. Our main result is that if the largeness condition is weakened slightly, then not only does the Razborov-Rudich proof break down, but such "almost-natural" (and useful) properties provably exist. Specifically, under the same pseudorandomness assumption that Razborov and Rudich make, a simple, explicit property that we call "discrimination" suffices to separate P/poly from NP; discrimination is nearly linear-time computable and almost large, having density 2^{-q(n)} where q is a quasi-polynomial function. For those who hope to separate P from NP using random function properties in some sense, discrimination is interesting, because it is constructive, yet may be thought of as a minor alteration of a property of a random function. The proof relies heavily on the self-defeating character of natural proofs. Our proof technique also yields an unconditional result, namely that there exist almost-large and useful properties that are constructive, if we are allowed to call non-uniform low-complexity classes "constructive." We note, though, that this unconditional result can also be proved by a more conventional counting argument. Finally, we give an alternative proof, communicated to us by Salil Vadhan at FOCS 2008, of one of our theorems, and we make some speculative remarks on the future prospects for proving strong circuit lower bounds.
Sociological Inequality and the Second Law
Venue: arXiv cs.IT 2009
Year: 2009

There are two fair ways to distribute particles in boxes. The first way is to divide the particles equally between the boxes. The second way, which is calculated here, is to score fairly the particles between the boxes. The obtained power law distribution function yields an uneven distribution of particles in boxes. It is shown that the obtained distribution fits well to sociological phenomena, such as the distribution of votes in polls and the distribution of wealth and Benford's law.
Bounds on the Sum Capacity of Synchronous Binary CDMA Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we obtain a family of lower bounds for the sum capacity of Code Division Multiple Access (CDMA) channels assuming binary inputs and binary signature codes in the presence of additive noise with an arbitrary distribution. The envelope of this family gives a relatively tight lower bound in terms of the number of users, spreading gain and the noise distribution. The derivation methods for the noiseless and the noisy channels are different but when the noise variance goes to zero, the noisy channel bound approaches the noiseless case. The behavior of the lower bound shows that for small noise power, the number of users can be much more than the spreading gain without any significant loss of information (overloaded CDMA). A conjectured upper bound is also derived under the usual assumption that the users send out equally likely binary bits in the presence of additive noise with an arbitrary distribution. As the noise level increases, and/or, the ratio of the number of users and the spreading gain increases, the conjectured upper bound approaches the lower bound. We have also derived asymptotic limits of our bounds that can be compared to a formula that Tanaka obtained using techniques from statistical physics; his bound is close to that of our conjectured upper bound for large scale systems.
Exposing Multi-Relational Networks to Single-Relational Network Analysis Algorithms
Venue: arXiv cs.DM 2009
Year: 2009

Many, if not most network analysis algorithms have been designed specifically for single-relational networks; that is, networks in which all edges are of the same type. For example, edges may either represent "friendship," "kinship," or "collaboration," but not all of them together. In contrast, a multi-relational network is a network with a heterogeneous set of edge labels which can represent relationships of various types in a single data structure. While multi-relational networks are more expressive in terms of the variety of relationships they can capture, there is a need for a general framework for transferring the many single-relational network analysis algorithms to the multi-relational domain. It is not sufficient to execute a single-relational network analysis algorithm on a multi-relational network by simply ignoring edge labels. This article presents an algebra for mapping multi-relational networks to single-relational networks, thereby exposing them to single-relational network analysis algorithms.
On the inner and outer bounds of 3-receiver broadcast channels with 2-degraded message sets
Venue: arXiv cs.IT 2009
Year: 2009

We consider a broadcast channel with 3 receivers and 2 messages (M0, M1) where two of the three receivers need to decode messages (M0, M1) while the remaining one just needs to decode the message M0. We study the best known inner and outer bounds under this setting, in an attempt to find the deficiencies with the current techniques of establishing the bounds. We produce a simple example where we are able to explicitly evaluate the inner bound and show that it differs from the general outer bound. For a class of channels where the general inner and outer bounds differ, we use a new argument to show that the inner bound is tight.
Hardness of embedding simplicial complexes in $\R^d$
Venue: arXiv cs.CG 2009
Year: 2009

Let EMBED(k,d) be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into R^d? Known results easily imply polynomiality of EMBED(k,2) (k=1,2; the case k=1, d=2 is graph planarity) and of EMBED(k,2k) for all k>2 (even if k is not considered fixed). We observe that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED(d,d) and EMBED(d-1,d) are undecidable for each d>4. Our main result is NP-hardness of EMBED(2,4) and, more generally, of EMBED(k,d) for all k,d with d>3 and d\geq k \geq (2d-2)/3. These dimensions fall outside the so-called metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spież, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range the deleted product obstruction is not sufficient to characterize embeddability.
Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
Venue: arXiv cs.DM 2009
Year: 2009

Let lambda_s(n) denote the maximum length of a Davenport-Schinzel sequence of order s on n symbols. For s=3 it is known that lambda_3(n) = Theta(n alpha(n)) (Hart and Sharir, 1986). For general s>=4 there are almost-tight upper and lower bounds, both of the form n * 2^poly(alpha(n)) (Agarwal, Sharir, and Shor, 1989). Our first result is an improvement of the upper-bound technique of Agarwal et al. We obtain improved upper bounds for s>=6, which are tight for even s up to lower-order terms in the exponent. More importantly, we also present a new technique for deriving upper bounds for lambda_s(n). With this new technique we: (1) re-derive the upper bound of lambda_3(n) <= 2n alpha(n) + O(n sqrt alpha(n)) (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport-Schinzel sequences considered by Adamec, Klazar, and Valtr (1992). Regarding lower bounds, we show that lambda_3(n) >= 2n alpha(n) - O(n), and therefore, the coefficient 2 is tight. We also present a simpler version of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds for even s>=4.
Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys
Venue: arXiv cs.CR 2009
Year: 2009

At Crypto'07, Goyal introduced the concept of Accountable Authority Identity-Based Encryption as a convenient tool to reduce the amount of trust in authorities in Identity-Based Encryption. In this model, if the Private Key Generator (PKG) maliciously re-distributes users' decryption keys, it runs the risk of being caught and prosecuted. Goyal proposed two constructions: the first one is efficient but can only trace well-formed decryption keys to their source; the second one allows tracing obfuscated decryption boxes in a model (called weak black-box model) where cheating authorities have no decryption oracle. The latter scheme is unfortunately far less efficient in terms of decryption cost and ciphertext size. In this work, we propose a new construction that combines the efficiency of Goyal's first proposal with a very simple weak black-box tracing mechanism. Our scheme is described in the selective-ID model but readily extends to meet all security properties in the adaptive-ID sense, which is not known to be true for prior black-box schemes.
A Non-Termination Criterion for Binary Constraint Logic Programs
Venue: arXiv cs.PL 2009
Year: 2009

On the one hand, termination analysis of logic programs is now a fairly established research topic within the logic programming community. On the other hand, non-termination analysis seems to remain a much less attractive subject. If we divide this line of research into two kinds of approaches: dynamic versus static analysis, this paper belongs to the latter. It proposes a criterion for detecting non-terminating atomic queries with respect to binary CLP rules, which strictly generalizes our previous works on this subject. We give a generic operational definition and an implemented logical form of this criterion. Then we show that the logical form is correct and complete with respect to the operational definition.
Positive factor networks: A graphical framework for modeling non-negative sequential data
Venue: arXiv cs.LG 2009
Year: 2009

We present a novel graphical framework for modeling non-negative sequential data with hierarchical structure. Our model corresponds to a network of coupled non-negative matrix factorization (NMF) modules, which we refer to as a positive factor network (PFN). The data model is linear, subject to non-negativity constraints, so that observation data consisting of an additive combination of individually representable observations is also representable by the network. This is a desirable property for modeling problems in computational auditory scene analysis, since distinct sound sources in the environment are often well-modeled as combining additively in the corresponding magnitude spectrogram. We propose inference and learning algorithms that leverage existing NMF algorithms and that are straightforward to implement. We present a target tracking example and provide results for synthetic observation data which serve to illustrate the interesting properties of PFNs and motivate their potential usefulness in applications such as music transcription, source separation, and speech recognition. We show how a target process characterized by a hierarchical state transition model can be represented as a PFN. Our results illustrate that a PFN which is defined in terms of a single target observation can then be used to effectively track the states of multiple simultaneous targets. Our results show that the quality of the inferred target states degrades gradually as the observation noise is increased. We also present results for an example in which meaningful hierarchical features are extracted from a spectrogram. Such a hierarchical representation could be useful for music transcription and source separation applications. We also propose a network for language modeling.
On Introspection, Metacognitive Control and Augmented Data Mining Live Cycles
Venue: arXiv cs.AI 2009
Year: 2009

We discuss metacognitive modelling as an enhancement to cognitive modelling and computing. Metacognitive control mechanisms should enable AI systems to self-reflect, reason about their actions, and to adapt to new situations. In this respect, we propose implementation details of a knowledge taxonomy and an augmented data mining life cycle which supports a live integration of obtained models.
On Transformations of Load-Store Maurer Instruction Set Architecture
Venue: arXiv cs.AR 2009
Year: 2009

In this paper, we study how certain conditions can affect the transformations on the states of the memory of a strict load-store Maurer ISA, when half of the data memory serves as the part of the operating unit.
Power Control in Cognitive Radio Networks: How to Cross a Multi-Lane Highway
Venue: arXiv cs.NI 2009
Year: 2009

We consider power control in cognitive radio networks where secondary users identify and exploit instantaneous and local spectrum opportunities without causing unacceptable interference to primary users. We qualitatively characterize the impact of the transmission power of secondary users on the occurrence of spectrum opportunities and the reliability of opportunity detection. Based on a Poisson model of the primary network, we quantify these impacts by showing that (i) the probability of spectrum opportunity decreases exponentially with respect to the transmission power of secondary users, where the exponential decay constant is given by the traffic load of primary users; (ii) reliable opportunity detection is achieved in the two extreme regimes in terms of the ratio between the transmission power of secondary users and that of primary users. Such analytical characterizations allow us to study power control for optimal transport throughput under constraints on the interference to primary users. Furthermore, we reveal the difference between detecting primary signals and detecting spectrum opportunities, and demonstrate the complex relationship between physical layer spectrum sensing and MAC layer throughput. The dependency of this PHY-MAC interaction on the application type and the use of handshake signaling such as RTS/CTS is illustrated.
How to Fully Exploit the Degrees of Freedom in the Downlink of MISO Systems With Opportunistic Beamforming
Venue: arXiv cs.IT 2009
Year: 2009

The opportunistic beamforming in the downlink of multiple-input single-output (MISO) systems forms $N$ transmit beams, usually, no more than the number of transmit antennas $N_t$. However, the degrees of freedom in this downlink is as large as $N_t^2$. That is, at most $N_t^2$ rather than only $N_t$ users can be simultaneously transmitted and thus the scheduling latency can be significantly reduced. In this paper, we focus on the opportunistic beamforming schemes with $N_t<N\le N_t^2$ transmit beams in the downlink of MISO systems over Rayleigh fading channels. We first show how to design the beamforming matrices with maximum number of transmit beams as well as least correlation between any pair of them as possible, through Fourier, Grassmannian, and mutually unbiased bases (MUB) based constructions in practice. Then, we analyze their system throughput by exploiting the asymptotic theory of extreme order statistics. Finally, our simulation results show the Grassmannian-based beamforming achieves the maximum throughput in all cases with $N_t=2$, 3, 4. However, if we want to exploit overall $N_t^2$ degrees of freedom, we shall resort to the Fourier and MUB-based constructions in the cases with $N_t=3$, 4, respectively.
Reduced Complexity Demodulation and Equalization Scheme for Differential Impulse Radio UWB Systems with ISI
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider the demodulation and equalization problem of differential Impulse Radio (IR) Ultra-WideBand (UWB) Systems with Inter-Symbol-Interference (ISI). The differential IR UWB systems have been extensively discussed recently. The advantage of differential IR UWB systems include simple receiver frontend structure. One challenge in the demodulation and equalization of such systems with ISI is that the systems have a rather complex model. The input and output signals of the systems follow a second-order Volterra model. Furthermore, the noise at the output is data dependent. In this paper, we propose a reduced-complexity joint demodulation and equalization algorithm. The algorithm is based on reformulating the nearest neighborhood decoding problem into a mixed quadratic programming and utilizing a semi-definite relaxation. The numerical results show that the proposed demodulation and equalization algorithm has low computational complexity, and at the same time, has almost the same error probability performance compared with the maximal likelihood decoding algorithm.
Superposition for Fixed Domains
Venue: arXiv cs.AI 2009
Year: 2009

Superposition is an established decision procedure for a variety of first-order logic theories represented by sets of clauses. A satisfiable theory, saturated by superposition, implicitly defines a minimal term-generated model for the theory. Proving universal properties with respect to a saturated theory directly leads to a modification of the minimal model's term-generated domain, as new Skolem functions are introduced. For many applications, this is not desired. Therefore, we propose the first superposition calculus that can explicitly represent existentially quantified variables and can thus compute with respect to a given domain. This calculus is sound and refutationally complete in the limit for a first-order fixed domain semantics. For saturated Horn theories and classes of positive formulas, we can even employ the calculus to prove properties of the minimal model itself, going beyond the scope of known superposition-based approaches.
Uncertainty Relations for Shift-Invariant Analog Signals
Venue: arXiv cs.IT 2009
Year: 2009

The past several years have witnessed a surge of research investigating various aspects of sparse representations and compressed sensing. Most of this work has focused on the finite-dimensional setting in which the goal is to decompose a finite-length vector into a given finite dictionary. Underlying many of these results is the conceptual notion of an uncertainty principle: a signal cannot be sparsely represented in two different bases. Here, we extend these ideas and results to the analog, infinite-dimensional setting by considering signals that lie in a finitely-generated shift-invariant (SI) space. This class of signals is rich enough to include many interesting special cases such as multiband signals and splines. By adapting the notion of coherence defined for finite dictionaries to infinite SI representations, we develop an uncertainty principle similar in spirit to its finite counterpart. We demonstrate tightness of our bound by considering a bandlimited lowpass train that achieves the uncertainty principle. Building upon these results and similar work in the finite setting, we show how to find a sparse decomposition in an overcomplete dictionary by solving a convex optimization problem. The distinguishing feature of our approach is the fact that even though the problem is defined over an infinite domain with infinitely many variables and constraints, under certain conditions on the dictionary spectrum our algorithm can find the sparsest representation by solving a finite-dimensional problem.
Formalising the pi-calculus using nominal logic
Venue: arXiv cs.LO 2009
Year: 2009

We formalise the pi-calculus using the nominal datatype package, based on ideas from the nominal logic by Pitts et al., and demonstrate an implementation in Isabelle/HOL. The purpose is to derive powerful induction rules for the semantics in order to conduct machine checkable proofs, closely following the intuitive arguments found in manual proofs. In this way we have covered many of the standard theorems of bisimulation equivalence and congruence, both late and early, and both strong and weak in a uniform manner. We thus provide one of the most extensive formalisations of a process calculus ever done inside a theorem prover. A significant gain in our formulation is that agents are identified up to alpha-equivalence, thereby greatly reducing the arguments about bound names. This is a normal strategy for manual proofs about the pi-calculus, but that kind of hand waving has previously been difficult to incorporate smoothly in an interactive theorem prover. We show how the nominal logic formalism and its support in Isabelle accomplishes this and thus significantly reduces the tedium of conducting completely formal proofs. This improves on previous work using weak higher order abstract syntax since we do not need extra assumptions to filter out exotic terms and can keep all arguments within a familiar first-order logic.
Planar Visibility Counting
Venue: arXiv cs.CG 2009
Year: 2009

For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.
On the Capacity of One-sided Two user Gaussian Fading Broadcast Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we investigate upper and lower bounds on the capacity of two-user fading broadcast channels where one of the users has a constant (non-fading) channel. We use the Costa entropy power inequality (EPI) along with an optimization framework to derive upper bounds on the sum-capacity and superposition coding to obtain lower bounds on the sum-rate for this channel. For this fading broadcast channel where one channel is constant, we find that the upper and lower bounds meet under special cases, and in general, we show that the achievable sum-rate comes within a constant of the outer bound.
Software Engineering & Systems Design Nature
Venue: arXiv cs.SE 2009
Year: 2009

The main problems of Software Engineering appear as a result of incompatibilities. For example, the quality of organization of the production process depends on correspondence with existent resources and on a common understanding of project goals by all team members. Software design is another example. Its successfulness rides on the architecture's conformity with a project's concepts. This is a point of great nicety. All elements should create a single space of interaction. And if the laws of such a space are imperfect, missequencing comes and the concept of a software system fails. We must do our best for this not to happen. To that end, having a subtle perception of systems structures is essential. Such knowledge can be based only on a fresh approach to the logical law.