OpenRaiser/Intern-Atlas huggingface dataset:
Algebraic Independence and Blackbox Identity Testing
Venue: arXiv cs.CC 2011
Year: 2011

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials {f_1, ..., f_m} \subset \F[x_1, ..., x_n] are called algebraically independent if there is no non-zero polynomial F such that F(f_1, ..., f_m) = 0. The transcendence degree, trdeg{f_1, ..., f_m}, is the maximal number r of algebraically independent polynomials in the set. In this paper we design blackbox and efficient linear maps ϕthat reduce the number of variables from n to r but maintain trdeg{ϕ(f_i)}_i = r, assuming f_i's sparse and small r. We apply these fundamental maps to solve several cases of blackbox identity testing: (1) Given a polynomial-degree circuit C and sparse polynomials f_1, ..., f_m with trdeg r, we can test blackbox D := C(f_1, ..., f_m) for zeroness in poly(size(D))^r time. (2) Define a spsp_δ(k,s,n) circuit C to be of the form \sum_{i=1}^k \prod_{j=1}^s f_{i,j}, where f_{i,j} are sparse n-variate polynomials of degree at most δ. For k = 2 we give a poly(snδ)^{δ^2} time blackbox identity test. (3) For a general depth-4 circuit we define a notion of rank. Assuming there is a rank bound R for minimal simple spsp_δ(k,s,n) identities, we give a poly(snRδ)^{Rkδ^2} time blackbox identity test for spsp_δ(k,s,n) circuits. This partially generalizes the state of the art of depth-3 to depth-4 circuits. The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.
On the Security of Index Coding with Side Information
Venue: arXiv cs.IT 2011
Year: 2011

Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix $L$, whose column space code $C(L)$ has length $n$, minimum distance $d$ and dual distance $d^\perp$, is $(d-1-t)$-block secure (and hence also weakly secure) if the adversary knows in advance $t \leq d-2$ messages, and is completely insecure if the adversary knows in advance more than $n - d$ messages. Strong security is examined under the conditions that the adversary: (i) possesses $t$ messages in advance; (ii) eavesdrops at most $μ$ transmissions; (iii) corrupts at most $δ$ transmissions. We prove that for sufficiently large $q$, an optimal linear index code which is strongly secure against such an adversary has length $κ_q+μ+2δ$. Here $κ_q$ is a generalization of the min-rank over $F_q$ of the side information graph for the ICSI problem in its original formulation in the work of Bar- Yossef et al.
Spatially Coupled Codes over the Multiple Access Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider spatially coupled code ensembles over a multiple access channel. Convolutional LDPC ensembles are one instance of spatially coupled codes. It was shown recently that, for transmission over the binary erasure channel, this coupling of individual code ensembles has the effect of increasing the belief propagation threshold of the coupled ensembles to the maximum a-posteriori threshold of the underlying ensemble. In this sense, spatially coupled codes were shown to be capacity achieving. It was observed, empirically, that these codes are universal in the sense that they achieve performance close to the Shannon threshold for any general binary-input memoryless symmetric channels. In this work we provide further evidence of the threshold saturation phenomena when transmitting over a class of multiple access channel. We show, by density evolution analysis and EXIT curves, that the belief propagation threshold of the coupled ensembles is very close to the ultimate Shannon limit.
The Asymptotic Limits of Interference in Multicell Networks with Channel Aware Scheduling
Venue: arXiv cs.IT 2011
Year: 2011

Interference is emerging as a fundamental bottleneck in many important wireless communication scenarios, including dense cellular networks and cognitive networks with spectrum sharing by multiple service providers. Although multipleantenna (MIMO) signal processing is known to offer useful degrees of freedom to cancel interference, extreme-value theoretic analysis recently showed that, even in the absence of MIMO processing, the scaling law of the capacity in the number of users for a multi-cell network with and without inter-cell interference was asymptotically identical provided a simple signal to noise and interference ratio (SINR) maximizing scheduler is exploited. This suggests that scheduling can help reduce inter-cell interference substantially, thus possibly limiting the need for multiple-antenna processing. However, the convergence limits of interference after scheduling in a multi-cell setting are not yet identified. In this paper1 we analyze such limits theoretically. We consider channel statistics under Rayleigh fading with equal path loss for all users or with unequal path loss. We uncover two surprisingly different behaviors for such systems. For the equal path loss case, we show that scheduling alone can cause the residual interference to converge to zero for large number of users. With unequal path loss however, the interference are shown to converge in average to a nonzero constant. Simulations back our findings.
Applications of Monotone Rank to Complexity Theory
Venue: arXiv cs.CC 2011
Year: 2011

Raz's recent result \cite{Raz2010} has rekindled people's interest in the study of \emph{tensor rank}, the generalization of matrix rank to high dimensions, by showing its connections to arithmetic formulas. In this paper, we follow Raz's work and show that \emph{monotone rank}, the monotone variant of tensor rank and matrix rank, has applications in algebraic complexity, quantum computing and communication complexity. This paper differs from Raz's paper in that it leverages existing results to show unconditional bounds while Raz's result relies on some assumptions. We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus provide a strong solution to Nisan's question \cite{Nis1991} in algebraic complexity. More specifically, we exhibit that there exists a homogeneous algebraic function $f$ of degree $d$ ($d$ even) on $n$ variables with the monotone algebraic branching program (ABP) complexity $Ω(d^2\log n)$ and the non-monotone ABP complexity $O(d^2)$. In Bell's theorem\cite{Bel1964, CHSH1969}, a basic assumption is that players have free will, and under such an assumption, local hidden variable theory still cannot predict the correlations produced by quantum mechanics. Using tools from monotone rank, we show that even if we disallow the players to have free will, local hidden variable theory still cannot predict the correlations produced by quantum mechanics. We generalize the log-rank conjecture \cite{LS1988} in communication complexity to the multiparty case, and prove that for super-polynomial parties, there is a super-polynomial separation between the deterministic communication complexity and the logarithm of the rank of the communication tensor. This means that the log-rank conjecture does not hold in high dimensions.
Tight Upper Bounds for Streett and Parity Complementation
Venue: arXiv cs.LO 2011
Year: 2011

Complementation of finite automata on infinite words is not only a fundamental problem in automata theory, but also serves as a cornerstone for solving numerous decision problems in mathematical logic, model-checking, program analysis and verification. For Streett complementation, a significant gap exists between the current lower bound $2^{Ω(n\lg nk)}$ and upper bound $2^{O(nk\lg nk)}$, where $n$ is the state size, $k$ is the number of Streett pairs, and $k$ can be as large as $2^{n}$. Determining the complexity of Streett complementation has been an open question since the late '80s. In this paper show a complementation construction with upper bound $2^{O(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{O(n^{2} \lg n)}$ for $k = ω(n)$, which matches well the lower bound obtained in \cite{CZ11a}. We also obtain a tight upper bound $2^{O(n \lg n)}$ for parity complementation.
A Tight Lower Bound for Streett Complementation
Venue: arXiv cs.LO 2011
Year: 2011

Finite automata on infinite words ($ω$-automata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of $ω$-automata is crucial in many of these applications. But the problem is non-trivial; even after extensive study during the past four decades, we still have an important type of $ω$-automata, namely Streett automata, for which the gap between the current best lower bound $2^{Ω(n \lg nk)}$ and upper bound $2^{Ω(nk \lg nk)}$ is substantial, for the Streett index size $k$ can be exponential in the number of states $n$. In arXiv:1102.2960 we showed a construction for complementing Streett automata with the upper bound $2^{O(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{O(n^{2} \lg n)}$ for $k=ω(n)$. In this paper we establish a matching lower bound $2^{Ω(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{Ω(n^{2} \lg n)}$ for $k = ω(n)$, and therefore showing that the construction is asymptotically optimal with respect to the $2^{Θ(\cdot)}$ notation.
Efficient and scalable geometric hashing method for searching protein 3D structures
Venue: arXiv cs.DB 2011
Year: 2011

As the structural databases continue to expand, efficient methods are required to search similar structures of the query structure from the database. There are many previous works about comparing protein 3D structures and scanning the database with a query structure. However, they generally have limitations on practical use because of large computational and storage requirements. We propose two new types of queries for searching similar sub-structures on the structural database: LSPM (Local Spatial Pattern Matching) and RLSPM (Reverse LSPM). Between two types of queries, we focus on RLSPM problem, because it is more practical and general than LSPM. As a naive algorithm, we adopt geometric hashing techniques to RLSPM problem and then propose our proposed algorithm which improves the baseline algorithm to deal with large-scale data and provide an efficient matching algorithm. We employ the sub-sampling and Z-ordering to reduce the storage requirement and execution time, respectively. We conduct our experiments to show the correctness and reliability of the proposed method. Our experiment shows that the true positive rate is at least 0.8 using the reliability measure.
Hybrid Model for Solving Multi-Objective Problems Using Evolutionary Algorithm and Tabu Search
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents a new multi-objective hybrid model that makes cooperation between the strength of research of neighborhood methods presented by the tabu search (TS) and the important exploration capacity of evolutionary algorithm. This model was implemented and tested in benchmark functions (ZDT1, ZDT2, and ZDT3), using a network of computers.
Sidon Sequences and Doubly Periodic Two-Dimensional Synchronization Patterns
Venue: arXiv cs.IT 2011
Year: 2011

Sidon sequences and their generalizations have found during the years and especially recently various applications in coding theory. One of the most important applications of these sequences is in the connection of synchronization patterns. A few constructions of two-dimensional synchronization patterns are based on these sequences. In this paper we present sufficient conditions that a two-dimensional synchronization pattern can be transformed into a Sidon sequence. We also present a new construction for Sidon sequences over an alphabet of size q(q-1), where q is a power of a prime.
Content replication and placement in mobile networks
Venue: arXiv cs.NI 2011
Year: 2011

Performance and reliability of content access in mobile networks is conditioned by the number and location of content replicas deployed at the network nodes. Location theory has been the traditional, centralized approach to study content replication: computing the number and placement of replicas in a static network can be cast as a facility location problem. The endeavor of this work is to design a practical solution to the above joint optimization problem that is suitable for mobile wireless environments. We thus seek a replication algorithm that is lightweight, distributed, and reactive to network dynamics. We devise a solution that lets nodes (i) share the burden of storing and providing content, so as to achieve load balancing, and (ii) autonomously decide whether to replicate or drop the information, so as to adapt the content availability to dynamic demands and time-varying network topologies. We evaluate our mechanism through simulation, by exploring a wide range of settings, including different node mobility models, content characteristics and system scales. Furthermore, we compare our mechanism to state-of-the-art approaches to content delivery in static and mobile networks. Results show that our mechanism, which uses local measurements only, is: (i) extremely precise in approximating an optimal solution to content placement and replication; (ii) robust against network mobility; (iii) flexible in accommodating various content access patterns. Moreover, our scheme outperforms alternative approaches to content dissemination both in terms of content access delay and access congestion.
Interference Two-Way Relay Channel with Three End-nodes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study a communication system consisting of three end-nodes, e.g. a single transceiver base station (BS), one transmitting and one receiving user equipments (UEs), and a common two-way relay node (RN) wherein the full-duplex BS transmits to the receiving UE in downlink direction and receives from the transmitting UE in uplink direction with the help of the intermediate full-duplex RN. We call this system model as interference two-way relay channel (ITWRC) with three end-nodes. Information theoretic bounds corresponding this system model are derived and analyzed so as to better understand the potentials of exploiting RN in future communication systems. Specifically, achievable rate regions corresponding to decode-and-forward (DF) relaying with and without rate splitting, and partial-DF and compress-and-forward (pDF+CF) relaying strategies are derived.
On the Capacity of Abelian Group Codes Over Discrete Memoryless Channels
Venue: arXiv cs.IT 2011
Year: 2011

For most discrete memoryless channels, there does not exist a linear code for the channel which uses all of the channel's input symbols. Therefore, linearity of the code for such channels is a very restrictive condition and there should be a loosening of the algebraic structure of the code to a degree that the code can admit any channel input alphabet. For any channel input alphabet size, there always exists an Abelian group structure defined on the alphabet. We investigate the capacity of Abelian group codes over discrete memoryless channels and provide lower and upper bounds on the capacity.
A family of fast-decodable MIDO codes from crossed-product algebras over Q
Venue: arXiv cs.IT 2011
Year: 2011

Multiple Input Double Output (MIDO) asymmetric space-time codes for 4 transmit antennas and 2 receive antennas can be employed in the downlink from base stations to portable devices. Previous MIDO code constructions with low Maximum Likelihood (ML) decoding complexity, full diversity and the non-vanishing determinant (NVD) property are mostly based on cyclic division algebras. In this paper, a new family of MIDO codes with the NVD property based on crossed-product algebras over Q is introduced. Fast decodability follows naturally from the structure of the codewords which consist of four generalized Alamouti blocks. The associated ML complexity order is the lowest known for full-rate MIDO codes (O(M^{10}) instead of O(M^{16}) with respect to the real constellation size M). Numerical simulations show that these codes have a performance from comparable up to 1dB gain compared to the best known MIDO code with the same complexity.
Using physiological measures in conjunction with other UX approaches for better understanding of the player's gameplay experiences
Venue: arXiv cs.HC 2011
Year: 2011

The goal of video games is to challenge and entertain the players. Successful video games deliver experience that impact players on a level of arousal. Therefore undertaking a user experience (UX) study is crucial to ensure that a game achieves both critical and financial success. However, traditional usability methods (observation, subjective reporting, questionnaire, and interview) have a number of limitations on game user research. In this study we capture player's physiological measures during a gameplay session, to indicate micro-events that have caused changes in their body signals. At the post-gameplay interviews we ask participants to comment and describe their feelings on the selected events. The aim of this study is not to over-interpret physiological measures, but on using blips in measures to help identify key points in a game, which we then use to investigate further with the participant. This approach provides a method that can identify not only the negative user experience and usability issues but also the events which have a positive impact on player's experience.
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
Venue: arXiv cs.DS 2011
Year: 2011

We study frequency allocation in wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells. In each vertex we have a certain number of requests, and each of those requests must be assigned a different frequency. Edges represent conflicts between cells, meaning that frequencies in adjacent vertices must be different as well. The objective is to minimize the total number of used frequencies. The offline version of the problem is known to be NP-hard. In the incremental version, requests for frequencies arrive over time and the algorithm is required to assign a frequency to a request as soon as it arrives. Competitive incremental algorithms have been studied for several classes of graphs. For paths, the optimal (asymptotic) ratio is known to be 4/3, while for hexagonal-cell graphs it is between 1.5 and 1.9126. For k-colorable graphs, the ratio of (k+1)/2 can be achieved. In this paper, we prove nearly tight bounds on the asymptotic competitive ratio for bipartite graphs, showing that it is between 1.428 and 1.433. This improves the previous lower bound of 4/3 and upper bound of 1.5. Our proofs are based on reducing the incremental problem to a purely combinatorial (equivalent) problem of constructing set families with certain intersection properties.
A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids
Venue: arXiv cs.DS 2011
Year: 2011

We give a simple polynomial time approximation scheme for the weighted matroid matching problem on strongly base orderable matroids. We also show that even the unweighted version of this problem is NP-complete and not in oracle-coNP.
Spatial SINR Games of Base Station Placement and Mobile Association
Venue: arXiv cs.NI 2011
Year: 2011

We study the question of determining locations of base stations that may belong to the same or to competing service providers. We take into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the base station that offers the best utility. The signal to interference and noise ratio is used as the quantity that determines the association. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e., the locations at which mobile terminals prefer to connect to a given base station than to others. We make some surprising observations: (i) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; (ii) A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the hierarchical equilibrium in the combined BS location and mobile association problem: we determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider hierarchical equilibria in two frequency systems with successive interference cancellation.
Foundations for Understanding and Building Conscious Systems using Stable Parallel Looped Dynamics
Venue: arXiv cs.AI 2011
Year: 2011

The problem of consciousness faced several challenges for a few reasons: (a) a lack of necessary and sufficient conditions, without which we would not know how close we are to the solution, (b) a lack of a synthesis framework to build conscious systems and (c) a lack of mechanisms explaining the transition between the lower-level chemical dynamics and the higher-level abstractions. In this paper, I address these issues using a new framework. The central result is that a person is 'minimally' conscious if and only if he knows at least one truth. This lets us move away from the vagueness surrounding consciousness and instead focus equivalently on: (i) what truths are and how our brain represents/relates them to each other and (ii) how we attain a feeling of knowing for a truth. For the former problem, since truths are things that do not change, I replace the abstract notion with a dynamical one called fixed sets. These sets are guaranteed to exist for our brain and other stable parallel looped systems. The relationships between everyday events are now built using relationships between fixed sets, until our brain creates a unique dynamical state called the self-sustaining threshold 'membrane' of fixed sets. For the latter problem, I present necessary and sufficient conditions for attaining a feeling of knowing using a definition of continuity applied to abstractions. Combining these results, I now say that a person is minimally conscious if and only if his brain has a self-sustaining dynamical membrane with abstract continuous paths. A synthetic system built to satisfy this equivalent self-sustaining membrane condition appears indistinguishable from human consciousness.
Enumeration and Decidable Properties of Automatic Sequences
Venue: arXiv cs.FL 2011
Year: 2011

We show that various aspects of k-automatic sequences -- such as having an unbordered factor of length n -- are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.
On the Implementation of Dynamic Patterns
Venue: arXiv cs.LO 2011
Year: 2011

The evaluation mechanism of pattern matching with dynamic patterns is modelled in the Pure Pattern Calculus by one single meta-rule. This contribution presents a refinement which narrows the gap between the abstract calculus and its implementation. A calculus is designed to allow reasoning on matching algorithms. The new calculus is proved to be confluent, and to simulate the original Pure Pattern Calculus. A family of new, matching-driven, reduction strategies is proposed.