OpenRaiser/Intern-Atlas huggingface dataset:
On Problems as Hard as CNFSAT
Venue: arXiv cs.DS 2014
Year: 2014

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including Graph Coloring, Hamiltonian Path, Dominating Set and 3-CNF-Sat. In some instances, improving these algorithms further seems to be out of reach. The CNF-Sat problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2^n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-Sat that run in time o(2^n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon<1, there is a (large) integer k such that that k-CNF-Sat cannot be computed in time 2^{epsilon n}. In this paper, we show that, for every epsilon < 1, the problems Hitting Set, Set Splitting, and NAE-Sat cannot be computed in time O(2^{epsilon n}) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for Set Cover, and prove that, under this assumption, the fastest known algorithms for Steinter Tree, Connected Vertex Cover, Set Partitioning, and the pseudo-polynomial time algorithm for Subset Sum cannot be significantly improved. Finally, we justify our assumption about the hardness of Set Cover by showing that the parity of the number of set covers cannot be computed in time O(2^{epsilon n}) for any epsilon<1 unless SETH fails.
Solution of the propeller conjecture in $\mathbb{R}^3$
Venue: arXiv cs.CC 2014
Year: 2014

It is shown that every measurable partition ${A_1,..., A_k}$ of $\mathbb{R}^3$ satisfies $$\sum_{i=1}^k||\int_{A_i} xe^{-\frac12||x||_2^2}dx||_2^2\le 9π^2.\qquad(*)$$ Let ${P_1,P_2,P_3}$ be the partition of $\mathbb{R}^2$ into $120^\circ$ sectors centered at the origin. The bound is sharp, with equality holding if $A_i=P_i\times \mathbb{R}$ for $i\in {1,2,3}$ and $A_i=\emptyset$ for $i\in \{4,...,k\}$ (up to measure zero corrections, orthogonal transformations and renumbering of the sets $\{A_1,...,A_k\}$). This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of $(*)$ is complexity-theoretic: the Unique Games hardness threshold of the Kernel Clustering problem with $4 \times 4$ centered and spherical hypothesis matrix equals $\frac{2π}{3}$.
The information path functional approach for solution of a controllable stochastic problem
Venue: arXiv cs.SY 2014
Year: 2014

We study a stochastic control system, described by Ito controllable equation, and evaluate the solutions by an entropy functional (EF), defined by the equation functions of controllable drift and diffusion. Considering a control problem for this functional, we solve the EF control variation problem (VP), which leads to both a dynamic approximation of the process entropy functional by an information path functional (IPF) and information dynamic model (IDM) of the stochastic process. The IPF variation equations allow finding the optimal control functions, applied to both stochastic system and the IDM for joint solution of the identification and optimal control problems, combined with state consolidation. In this optimal dual strategy, the IPF optimum predicts each current control action not only in terms of total functional path goal, but also by setting for each following control action the renovated values of this functional controllable drift and diffusion, identified during the optimal movement, which concurrently correct this goal. The VP information invariants allow optimal encoding of the identified dynamic model operator and control. The introduced method of cutting off the process by applying an impulse control estimates the cutoff information, accumulated by the process inner connections between its states. It has shown that such a functional information measure contains more information than the sum of Shannon entropies counted for all process separated states, and provides information measure of Feller kernel. Examples illustrate the procedure of solving these problems, which has been implemented in practice. Key words: Entropy and information path functionals, variation equations, information invariants, controllable dynamics, impulse controls, cutting off the diffusion process, identification, cooperation, encoding.
Four Layered Approach to Non-Functional Requirements Analysis
Venue: arXiv cs.SE 2014
Year: 2014

Identification of non-functional requirements is important for successful development and deployment of the software product. The acceptance of the software product by the customer depends on the non-functional requirements which are incorporated in the software. For this, we need to identify all the non-functional requirements required by all stakeholders. In the literature not many approaches are available for this purpose. Hence, we have proposed a four layered analysis approach for identification of non-functional requirements. The proposed layered approach has many advantages over non-layered approach. As part of this approach some rules are also proposed to be used in each layer. The approach is applied successfully on two case studies. The identified non-functional requirements are validated using a check list and in addition the completeness of the identified non-requirements is computed using a metric.
A Feasibility Test for Linear Interference Alignment in MIMO Channels with Constant Coefficients
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the feasibility of linear interference alignment (IA) for multiple-input multiple-output (MIMO) channels with constant coefficients for any number of users, antennas and streams per user; and propose a polynomial-time test for this problem. Combining algebraic geometry techniques with differential topology ones, we first prove a result that generalizes those previously published on this topic. Specifically, we consider the input set (complex projective space of MIMO interference channels), the output set (precoder and decoder Grassmannians) and the solution set (channels, decoders and precoders satisfying the IA polynomial equations), not only as algebraic sets but also as smooth compact manifolds. Using this mathematical framework, we prove that the linear alignment problem is feasible when the algebraic dimension of the solution variety is larger than or equal to the dimension of the input space and the linear mapping between the tangent spaces of both smooth manifolds given by the first projection is generically surjective. If that mapping is not surjective, then the solution variety projects into the input space in a singular way and the projection is a zero-measure set. This result naturally yields a simple feasibility test, which amounts to checking the rank of a matrix. We also provide an exact arithmetic version of the test, which proves that testing the feasibility of IA for generic MIMO channels belongs to the bounded-error probabilistic polynomial (BPP) complexity class.
Non-adaptive Group Testing: Explicit bounds and novel algorithms
Venue: arXiv cs.IT 2014
Year: 2014

We consider some computationally efficient and provably correct algorithms with near-optimal sample-complexity for the problem of noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be "sparse". We consider non-adaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the "Coupon Collector Algorithm", the "Column Matching Algorithms", and the "LP Decoding Algorithms" -- the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the Compressive Sensing literature. The second and third of these algorithms have several flavours, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds -- with all constants expressly computed -- for these algorithms as a function of the desired error probability; the noise parameters; the number of items; and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).
The Complexity of Computing the Sign of the Tutte Polynomial
Venue: arXiv cs.CC 2014
Year: 2014

We study the complexity of computing the sign of the Tutte polynomial of a graph. As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem. Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually #P-hard. As a trivial consequence, approximating the polynomial is also #P-hard in this case. Thus, approximately evaluating the Tutte polynomial in these regions is as hard as exactly counting the satisfying assignments to a CNF Boolean formula. For most other points in the parameter space, we show that computing the sign of the polynomial is in FP, whereas approximating the polynomial can be done in polynomial time with an NP oracle. As a special case, we completely resolve the complexity of computing the sign of the chromatic polynomial - this is easily computable at q=2 and when q is less than or equal to 32/27, and is NP-hard to compute for all other values of the parameter q.
Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives
Venue: arXiv cs.LO 2014
Year: 2014

We consider Markov decision processes (MDPs) with $ω$-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. The algorithms for the computation of the almost-sure winning set for parity objectives iteratively use the solutions for the almost-sure winning set for Büchi objectives (a special case of parity objectives). We study for the first time the average case complexity of the classical algorithm for computing almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, we show that for general MDPs the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given all graphs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.
An Algorithmic Characterization of Polynomial Functions over $Z_{p^n}$
Venue: arXiv cs.SC 2014
Year: 2014

In this paper we consider polynomial representability of functions defined over $Z_{p^n}$, where $p$ is a prime and $n$ is a positive integer. Our aim is to provide an algorithmic characterization that (i) answers the decision problem: to determine whether a given function over $Z_{p^n}$ is polynomially representable or not, and (ii) finds the polynomial if it is polynomially representable. The previous characterizations given by Kempner (1921) and Carlitz (1964) are existential in nature and only lead to an exhaustive search method, i.e., algorithm with complexity exponential in size of the input. Our characterization leads to an algorithm whose running time is linear in size of input. We also extend our result to the multivariate case.
Auditing for Distributed Storage Systems
Venue: arXiv cs.CR 2014
Year: 2014

Distributed storage codes have recently received a lot of attention in the community. Independently, another body of work has proposed integrity checking schemes for cloud storage, none of which, however, is customized for coding-based storage or can efficiently support repair. In this work, we bridge the gap between these two currently disconnected bodies of work. We propose NC-Audit, a novel cryptography-based remote data integrity checking scheme, designed specifically for network coding-based distributed storage systems. NC-Audit combines, for the first time, the following desired properties: (i) efficient checking of data integrity, (ii) efficient support for repairing failed nodes, and (iii) protection against information leakage when checking is performed by a third party. The key ingredient of the design of NC-Audit is a novel combination of SpaceMac, a homomorphic message authentication code (MAC) scheme for network coding, and NCrypt, a novel chosen-plaintext attack (CPA) secure encryption scheme that is compatible with SpaceMac. Our evaluation of a Java implementation of NC-Audit shows that an audit costs the storage node and the auditor a modest amount computation time and lower bandwidth than prior work.
Approximate Well-supported Nash Equilibria below Two-thirds
Venue: arXiv cs.GT 2014
Year: 2014

In an epsilon-Nash equilibrium, a player can gain at most epsilon by changing his behaviour. Recent work has addressed the question of how best to compute epsilon-Nash equilibria, and for what values of epsilon a polynomial-time algorithm exists. An epsilon-well-supported Nash equilibrium (epsilon-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most epsilon less than the best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.
On Capacity Regions of Discrete Asynchronous Multiple Access Channels
Venue: arXiv cs.IT 2014
Year: 2014

A general formalization is given for asynchronous multiple access channels which admits different assumptions on delays. This general framework allows the analysis of so far unexplored models leading to new interesting capacity regions. In particular, a single letter characterization is given for the capacity region in case of 3 senders, 2 synchronous with each other and the third not synchronous with them.
An Equilibrium Analysis of Scrip Systems
Venue: arXiv cs.GT 2014
Year: 2014

A game-theoretic model of scrip (artificial currency) systems is analyzed. It is shown that relative entropy can be used to characterize the distribution of agent wealth when all agents use threshold strategies---that is, they volunteer to do work iff they have below a threshold amount of money. Monotonicity of agents' best-reply functions is used to show that scrip systems have pure strategy equilibria where all agents use threshold strategies. An algorithm is given that can compute such an equilibrium and the resulting distribution of wealth.
Converging to the Chase - a Tool for Finite Controllability
Venue: arXiv cs.DB 2014
Year: 2014

We solve a problem, stated in [CGP10], showing that Sticky Datalog, defined in the cited paper as an element of the Datalog\pm project, has the finite controllability property. In order to do that, we develop a technique, which we believe can have further applications, of approximating Chase(D, T), for a database instance D and some sets of tuple generating dependencies T, by an infinite sequence of finite structures, all of them being models of T.
Posterior Matching Scheme for Gaussian Multiple Access Channel with Feedback
Venue: arXiv cs.IT 2014
Year: 2014

Posterior matching is a method proposed by Ofer Shayevitz and Meir Feder to design capacity achieving coding schemes for general point-to-point memoryless channels with feedback. In this paper, we present a way to extend posterior matching based encoding and variable rate decoding ideas for the Gaussian MAC with feedback, referred to as time-varying posterior matching scheme, analyze the achievable rate region and error probabilities of the extended encoding-decoding scheme. The time-varying posterior matching scheme is a generalization of the Shayevitz and Feder's posterior matching scheme when the posterior distributions of the input messages given output are not fixed over transmission time slots. It turns out that the well-known Ozarow's encoding scheme, which obtains the capacity of two-user Gaussian channel, is a special case of our extended posterior matching framework as the Schalkwijk-Kailath's scheme is a special case of the point-to-point posterior matching mentioned above. Furthermore, our designed posterior matching also obtains the linear-feedback sum-capacity for the symmetric multiuser Gaussian MAC. Besides, the encoding scheme in this paper is designed for the real Gaussian MAC to obtain that performance, which is different from previous approaches where encoding schemes are designed for the complex Gaussian MAC. More importantly, this paper shows potential of posterior matching in designing optimal coding schemes for multiuser channels with feedback.
On the Complexity of the Monte Carlo Method for Incremental PageRank
Venue: arXiv cs.DS 2014
Year: 2014

This note extends the analysis of incremental PageRank in [B. Bahmani, A. Chowdhury, and A. Goel. Fast Incremental and Personalized PageRank. VLDB 2011]. In that work, the authors prove a running time of $O(\frac{nR}{ε^2} \ln(m))$ to keep PageRank updated over $m$ edge arrivals in a graph with $n$ nodes when the algorithm stores $R$ random walks per node and the PageRank teleport probability is $ε$. To prove this running time, they assume that edges arrive in a random order, and leave it to future work to extend their running time guarantees to adversarial edge arrival. In this note, we show that the random edge order assumption is necessary by exhibiting a graph and adversarial edge arrival order in which the running time is $Ω\left(R n m^{\lg{\frac{3}{2}(1-ε)}}\right)$. More generally, for any integer $d \geq 2$, we construct a graph and adversarial edge order in which the running time is $Ω\left(R n m^{\log_d(H_d (1-ε))}\right)$, where $H_d$ is the $d$th harmonic number.
Constraint LTL Satisfiability Checking without Automata
Venue: arXiv cs.LO 2014
Year: 2014

This paper introduces a novel technique to decide the satisfiability of formulae written in the language of Linear Temporal Logic with Both future and past operators and atomic formulae belonging to constraint system D (CLTLB(D) for short). The technique is based on the concept of bounded satisfiability, and hinges on an encoding of CLTLB(D) formulae into QF-EUD, the theory of quantifier-free equality and uninterpreted functions combined with D. Similarly to standard LTL, where bounded model-checking and SAT-solvers can be used as an alternative to automata-theoretic approaches to model-checking, our approach allows users to solve the satisfiability problem for CLTLB(D) formulae through SMT-solving techniques, rather than by checking the emptiness of the language of a suitable automaton A_ϕ. The technique is effective, and it has been implemented in our Zot formal verification tool.
Partial-MDS Codes and their Application to RAID Type of Architectures
Venue: arXiv cs.IT 2014
Year: 2014

A family of codes with a natural two-dimensional structure is presented, inspired by an application of RAID type of architectures whose units are solid state drives (SSDs). Arrays of SSDs behave differently to arrays of hard disk drives (HDDs), since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial-MDS (PMDS) codes.
Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2014
Year: 2014

Given a graph $G$ and an integer $k$, the Feedback Vertex Set (FVS) problem asks if there is a vertex set $T$ of size at most $k$ that hits all cycles in the graph. The fixed-parameter tractability status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08) showed that it is FPT by giving a $4^{k}k!n^{O(1)}$ time algorithm. In the subset versions of this problems, we are given an additional subset $S$ of vertices (resp., edges) and we want to hit all cycles passing through a vertex of $S$ (resp. an edge of $S$). Recently, the Subset Feedback Vertex Set in undirected graphs was shown to be FPT by Cygan et al. (ICALP '11) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that Subset Feedback Vertex Set in directed graphs can be solved in time $2^{O(k^3)}n^{O(1)}$. By our result, we complete the picture for feedback vertex set problems and their subset versions in undirected and directed graphs. Besides proving the fixed-parameter tractability of Directed Subset Feedback Vertex Set, we reformulate the random sampling of important separators technique in an abstract way that can be used for a general family of transversal problems. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from $2^{2^{O(k)}}$ to $2^{O(k^2)}$ in the parameter dependence of the Directed Multiway Cut algorithm of Chitnis et al. (SODA '12).
Sharp recovery bounds for convex demixing, with applications
Venue: arXiv cs.IT 2014
Year: 2014

Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model which ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (i) demixing two signals that are sparse in mutually incoherent bases; (ii) decoding spread-spectrum transmissions in the presence of impulsive errors; and (iii) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.