OpenRaiser/Intern-Atlas huggingface dataset:
Nomographic Functions: Efficient Computation in Clustered Gaussian Sensor Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a clustered wireless sensor network is considered that is modeled as a set of coupled Gaussian multiple-access channels. The objective of the network is not to reconstruct individual sensor readings at designated fusion centers but rather to reliably compute some functions thereof. Our particular attention is on real-valued functions that can be represented as a post-processed sum of pre-processed sensor readings. Such functions are called nomographic functions and their special structure permits the utilization of the interference property of the Gaussian multiple-access channel to reliably compute many linear and nonlinear functions at significantly higher rates than those achievable with standard schemes that combat interference. Motivated by this observation, a computation scheme is proposed that combines a suitable data pre- and post-processing strategy with a nested lattice code designed to protect the sum of pre-processed sensor readings against the channel noise. After analyzing its computation rate performance, it is shown that at the cost of a reduced rate, the scheme can be extended to compute every continuous function of the sensor readings in a finite succession of steps, where in each step a different nomographic function is computed. This demonstrates the fundamental role of nomographic representations.
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Venue: arXiv cs.GT 2014
Year: 2014

We study the deterministic and randomized query complexity of finding approximate equilibria in bimatrix games. We show that the deterministic query complexity of finding an $ε$-Nash equilibrium when $ε< \frac{1}{2}$ is $Ω(k^2)$, even in zero-one constant-sum games. In combination with previous results \cite{FGGS13}, this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a $(\frac{3 - \sqrt{5}}{2} + ε)$-Nash equilibrium using $O(\frac{k \cdot \log k}{ε^2})$ payoff queries, which shows that the $\frac{1}{2}$ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an $ε$-WSNE of a zero-sum bimatrix game using $O(\frac{k \cdot \log k}{ε^4})$ payoff queries, and we then use this to obtain a randomized algorithm for finding a $(\frac{2}{3} + ε)$-WSNE in a general bimatrix game using $O(\frac{k \cdot \log k}{ε^4})$ payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require $Ω(k^2)$ payoff queries in order to find a $\frac{1}{6k}$-Nash equilibrium, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.
User Selection in MIMO Interfering Broadcast Channels
Venue: arXiv cs.IT 2014
Year: 2014

Interference alignment aims to achieve maximum degrees of freedom in an interference system. For achieving Interference alignment in interfering broadcast systems a closed-form solution is proposed in [1] which is an extension of the grouping scheme in [2]. In a downlink scenario where there are a large number of users, the base station is required to select a subset of users such that the sum rate is maximized. To search for the optimal user subset using brute-force approach is computationally exhaustive because of the large number of possible user subset combinations. We propose a user selection algorithm achieving sum rate close to that of optimal solution. The algorithm employs coordinate ascent approach and exploits orthogonality between the desired signal space and the interference channel space in the reciprocal system to select the user at each step. For the sake of completeness, we have also extended the sum rate approach based algorithm to Interfering broadcast channel. The complexity of both these algorithms is shown to be linear with respect to the total number of users as compared to exponential in brute-force search.
Data Framing Attack on State Estimation
Venue: arXiv cs.CR 2014
Year: 2014

A new mechanism aimed at misleading a power system control center about the source of a data attack is proposed. As a man-in-the-middle state attack, a data framing attack is proposed to exploit the bad data detection and identification mechanisms currently in use at most control centers. In particular, the proposed attack frames meters that are providing correct data as sources of bad data such that the control center will remove useful measurements that would otherwise be used by the state estimator. The optimal design of a data framing attack is formulated as a quadratically constrained quadratic program (QCQP). It is shown that the proposed attack is capable of perturbing the power system state estimate by an arbitrary degree controlling only half of a critical set of measurements that are needed to make a system unobservable. Implications of this attack on power system operations are discussed, and the attack performance is evaluated using benchmark systems.
Hardness measures and resolution lower bounds
Venue: arXiv cs.CC 2014
Year: 2014

Various "hardness" measures have been studied for resolution, providing theoretical insight into the proof complexity of resolution and its fragments, as well as explanations for the hardness of instances in SAT solving. In this report we aim at a unified view of a number of hardness measures, including different measures of width, space and size of resolution proofs. We also extend these measures to all clause-sets (possibly satisfiable).
Guaranteed Collision Detection With Toleranced Motions
Venue: arXiv cs.CG 2014
Year: 2014

We present a method for guaranteed collision detection with toleranced motions. The basic idea is to consider the motion as a curve in the 12-dimensional space of affine displacements, endowed with an object-oriented Euclidean metric, and cover it with balls. The associated orbits of points, lines, planes and polygons have particularly simple shapes that lend themselves well to exact and fast collision queries. We present formulas for elementary collision tests with these orbit shapes and we suggest an algorithm, based on motion subdivision and computation of bounding balls, that can give a no-collision guarantee. It allows a robust and efficient implementation and parallelization. At hand of several examples we explore the asymptotic behavior of the algorithm and compare different implementation strategies.
b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
Venue: arXiv cs.CC 2014
Year: 2014

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χ_b(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it admits a b-coloring with t colors, for every t = χ(G),\ldots,χ_b(G), and b-monotonic if χ_b(H_1) \geq χ_b(H_2) for every induced subgraph H_1 of G, and every induced subgraph H_2 of H_1. We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: - We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. - We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at most a given threshold. - We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. - Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic.
Distributed simulation of polychronous and plastic spiking neural networks: strong and weak scaling of a representative mini-application benchmark executed on a small-scale commodity cluster
Venue: arXiv cs.DC 2014
Year: 2014

We introduce a natively distributed mini-application benchmark representative of plastic spiking neural network simulators. It can be used to measure performances of existing computing platforms and to drive the development of future parallel/distributed computing systems dedicated to the simulation of plastic spiking networks. The mini-application is designed to generate spiking behaviors and synaptic connectivity that do not change when the number of hardware processing nodes is varied, simplifying the quantitative study of scalability on commodity and custom architectures. Here, we present the strong and weak scaling and the profiling of the computational/communication components of the DPSNN-STDP benchmark (Distributed Simulation of Polychronous Spiking Neural Network with synaptic Spike-Timing Dependent Plasticity). In this first test, we used the benchmark to exercise a small-scale cluster of commodity processors (varying the number of used physical cores from 1 to 128). The cluster was interconnected through a commodity network. Bidimensional grids of columns composed of Izhikevich neurons projected synapses locally and toward first, second and third neighboring columns. The size of the simulated network varied from 6.6 Giga synapses down to 200 K synapses. The code demonstrated to be fast and scalable: 10 wall clock seconds were required to simulate one second of activity and plasticity (per Hertz of average firing rate) of a network composed by 3.2 G synapses running on 128 hardware cores clocked @ 2.4 GHz. The mini-application has been designed to be easily interfaced with standard and custom software and hardware communication interfaces. It has been designed from its foundation to be natively distributed and parallel, and should not pose major obstacles against distribution and parallelization on several platforms.
A Study On ID-based Authentication Schemes for Telecare Medical Information System
Venue: arXiv cs.CR 2014
Year: 2014

The smart card based authentication schemes are designed and developed to ensure secure and authorized communication between remote user and the server. In recent times, many smart card based authentication schemes for the telecare medical information systems (TMIS) have been presented. In this article, we briefly discuss some of the recently published smart card based authentication schemes for TMIS and try to show why efficient login and password change phases are required. In other word, the study demonstrates how inefficient password change phase leads to denial of server attack and how inefficient login phase increase the communication and computation overhead and decrease the performance of the system.
In-Band Full-Duplex Wireless: Challenges and Opportunities
Venue: arXiv cs.IT 2014
Year: 2014

In-band full-duplex (IBFD) operation has emerged as an attractive solution for increasing the throughput of wireless communication systems and networks. With IBFD, a wireless terminal is allowed to transmit and receive simultaneously in the same frequency band. This tutorial paper reviews the main concepts of IBFD wireless. Because one the biggest practical impediments to IBFD operation is the presence of self-interference, i.e., the interference caused by an IBFD node's own transmissions to its desired receptions, this tutorial surveys a wide range of IBFD self-interference mitigation techniques. Also discussed are numerous other research challenges and opportunities in the design and analysis of IBFD wireless systems.
A Discontinuous Galerkin Time Domain Framework for Periodic Structures Subject To Oblique Excitation
Venue: arXiv cs.CE 2014
Year: 2014

A nodal Discontinuous Galerkin (DG) method is derived for the analysis of time-domain (TD) scattering from doubly periodic PEC/dielectric structures under oblique interrogation. Field transformations are employed to elaborate a formalism that is free from any issues with causality that are common when applying spatial periodic boundary conditions simultaneously with incident fields at arbitrary angles of incidence. An upwind numerical flux is derived for the transformed variables, which retains the same form as it does in the original Maxwell problem for domains without explicitly imposed periodicity. This, in conjunction with the amenability of the DG framework to non-conformal meshes, provides a natural means of accurately solving the first order TD Maxwell equations for a number of periodic systems of engineering interest. Results are presented that substantiate the accuracy and utility of our method.
Generalized Instantly Decodable Network Coding for Relay-Assisted Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we investigate the problem of minimizing the frame completion delay for Instantly Decodable Network Coding (IDNC) in relay-assisted wireless multicast networks. We first propose a packet recovery algorithm in the single relay topology which employs generalized IDNC instead of strict IDNC previously proposed in the literature for the same relay-assisted topology. This use of generalized IDNC is supported by showing that it is a super-set of the strict IDNC scheme, and thus can generate coding combinations that are at least as efficient as strict IDNC in reducing the average completion delay. We then extend our study to the multiple relay topology and propose a joint generalized IDNC and relay selection algorithm. This proposed algorithm benefits from the reception diversity of the multiple relays to further reduce the average completion delay in the network. Simulation results show that our proposed solutions achieve much better performance compared to previous solutions in the literature.
Submodularization for Quadratic Pseudo-Boolean Optimization
Venue: arXiv cs.CV 2014
Year: 2014

Many computer vision problems require optimization of binary non-submodular energies. We propose a general optimization framework based on local submodular approximations (LSA). Unlike standard LP relaxation methods that linearize the whole energy globally, our approach iteratively approximates the energies locally. On the other hand, unlike standard local optimization methods (e.g. gradient descent or projection techniques) we use non-linear submodular approximations and optimize them without leaving the domain of integer solutions. We discuss two specific LSA algorithms based on "trust region" and "auxiliary function" principles, LSA-TR and LSA-AUX. These methods obtain state-of-the-art results on a wide range of applications outperforming many standard techniques such as LBP, QPBO, and TRWS. While our paper is focused on pairwise energies, our ideas extend to higher-order problems. The code is available online (http://vision.csd.uwo.ca/code/).
A Simple, Faster Method for Kinetic Proximity Problems
Venue: arXiv cs.CG 2014
Year: 2014

For a set of $n$ points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDS's for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph. We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDS's that efficiently maintain these sparse graphs on a set of $n$ moving points, where the trajectory of each point is assumed to be an algebraic function of constant maximum degree $s$. We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDS's use $O(n)$ space and $O(n\log n)$ preprocessing time. We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes $O(n^2β_{2s+2}(n))$ (resp. $O(n^3β_{2s+2}^2(n)\log n)$) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in time $O(\log n)$ in an amortized sense. Here, $β_s(n)$ is an extremely slow-growing function. Our KDS for maintenance of all the nearest neighbors and the closest pair processes $O(n^2β^2_{2s+2}(n)\log n)$ events. For maintenance of the EMST, our KDS processes $O(n^3β_{2s+2}^2(n)\log n)$ events. For all three of these problems, each event can be handled in time $O(\log n)$ in an amortized sense. We improve the previous randomized kinetic algorithm for maintenance of all the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS by Rahmati and Zarei.
Minimum Bisection is fixed parameter tractable
Venue: arXiv cs.DS 2014
Year: 2014

In the classic Minimum Bisection problem we are given as input a graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $O(2^{O(k^{3})}n^3 \log^3 n)$. This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most $k$ edges.
Quantifying unique information
Venue: arXiv cs.IT 2014
Year: 2014

We propose new measures of shared information, unique information and synergistic information that can be used to decompose the multi-information of a pair of random variables $(Y,Z)$ with a third random variable $X$. Our measures are motivated by an operational idea of unique information which suggests that shared information and unique information should depend only on the pair marginal distributions of $(X,Y)$ and $(X,Z)$. Although this invariance property has not been studied before, it is satisfied by other proposed measures of shared information. The invariance property does not uniquely determine our new measures, but it implies that the functions that we define are bounds to any other measures satisfying the same invariance property. We study properties of our measures and compare them to other candidate measures.
Ranking users, papers and authors in online scientific communities
Venue: arXiv cs.SI 2014
Year: 2014

The ever-increasing quantity and complexity of scientific production have made it difficult for researchers to keep track of advances in their own fields. This, together with growing popularity of online scientific communities, calls for the development of effective information filtering tools. We propose here a method to simultaneously compute reputation of users and quality of scientific artifacts in an online scientific community. Evaluation on artificially-generated data and real data from the Econophysics Forum is used to determine the method's best-performing variants. We show that when the method is extended by considering author credit, its performance improves on multiple levels. In particular, top papers have higher citation count and top authors have higher $h$-index than top papers and top authors chosen by other algorithms.
Smoothed Analysis of Tensor Decompositions
Venue: arXiv cs.DS 2014
Year: 2014

Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we show that our algorithm is robust to inverse polynomial error -- a crucial property for applications in learning since we are only allowed a polynomial number of samples. While algorithms are known for exact tensor decomposition in some overcomplete settings, our main contribution is in analyzing their stability in the framework of smoothed analysis. Our main technical contribution is to show that tensor products of perturbed vectors are linearly independent in a robust sense (i.e. the associated matrix has singular values that are at least an inverse polynomial). This key result paves the way for applying tensor methods to learning problems in the smoothed setting. In particular, we use it to obtain results for learning multi-view models and mixtures of axis-aligned Gaussians where there are many more "components" than dimensions. The assumption here is that the model is not adversarially chosen, formalized by a perturbation of model parameters. We believe this an appealing way to analyze realistic instances of learning problems, since this framework allows us to overcome many of the usual limitations of using tensor methods.
FPTAS for Counting Monotone CNF
Venue: arXiv cs.DS 2014
Year: 2014

A monotone CNF formula is a Boolean formula in conjunctive normal form where each variable appears positively. We design a deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of satisfying assignments for a given monotone CNF formula when each variable appears in at most $5$ clauses. Equivalently, this is also an FPTAS for counting set covers where each set contains at most $5$ elements. If we allow variables to appear in a maximum of $6$ clauses (or sets to contain $6$ elements), it is NP-hard to approximate it. Thus, this gives a complete understanding of the approximability of counting for monotone CNF formulas. It is also an important step towards a complete characterization of the approximability for all bounded degree Boolean #CSP problems. In addition, we study the hypergraph matching problem, which arises naturally towards a complete classification of bounded degree Boolean #CSP problems, and show an FPTAS for counting 3D matchings of hypergraphs with maximum degree $4$. Our main technique is correlation decay, a powerful tool to design deterministic FPTAS for counting problems defined by local constraints among a number of variables. All previous uses of this design technique fall into two categories: each constraint involves at most two variables, such as independent set, coloring, and spin systems in general; or each variable appears in at most two constraints, such as matching, edge cover, and holant problem in general. The CNF problems studied here have more complicated structures than these problems and require new design and proof techniques. As it turns out, the technique we developed for the CNF problem also works for the hypergraph matching problem. We believe that it may also find applications in other CSP or more general counting problems.