Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Containment Problem for Linear Sets
256
0
0.0
(
0
)
Added by
Hans Simon
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Hans U. Simon
Ask ChatGPT about the research
No Arabic abstract
It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is $log$-complete in $Pi_2^p$. It had been shown quite recently that already the containment problem for multi-dimensional linear sets is $log$-complete in $Pi_2^p$ (where hardness even holds for a unary encoding of the numerical input parameters). In this paper, we show that already the containment problem for $1$-dimensional linear sets (with binary encoding of the numerical input parameters) is $log$-hard (and therefore also $log$-complete) in $Pi_2^p$. However, combining both restrictions (dimension $1$ and unary encoding), the problem becomes solvable in polynomial time.
rate research
Read More
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3, there exists a polynomial-time algorithm based on Lovasz theory of polymatroid matching. Here we give a completely different, randomized polynomial-time algorithm in the case k=3. The main ingredients are a Pfaffian formula by Vaintrob and one of the authors (G.M.) for a polynomial that enumerates spanning hypertrees with some signs, and a lemma on the number of roots of polynomials over a finite field.
In analogy with epsilon-biased sets over Z_2^n, we construct explicit epsilon-biased sets over nonabelian finite groups G. That is, we find sets S subset G such that | Exp_{x in S} rho(x)| <= epsilon for any nontrivial irreducible representation rho. Equivalently, such sets make Gs Cayley graph an expander with eigenvalue |lambda| <= epsilon. The Alon-Roichman theorem shows that random sets of size O(log |G| / epsilon^2) suffice. For groups of the form G = G_1 x ... x G_n, our construction has size poly(max_i |G_i|, n, epsilon^{-1}), and we show that a set S subset G^n considered by Meka and Zuckerman that fools read-once branching programs over G is also epsilon-biased in this sense. For solvable groups whose abelian quotients have constant exponent, we obtain epsilon-biased sets of size (log |G|)^{1+o(1)} poly(epsilon^{-1}). Our techniques include derandomized squaring (in both the matrix product and tensor product senses) and a Chernoff-like bound on the expected norm of the product of independently random operators that may be of independent interest.
Subsets of F_2^n that are eps-biased, meaning that the parity of any set of bits is even or odd with probability eps close to 1/2, are powerful tools for derandomization. A simple randomized construction shows that such sets exist of size O(n/eps^2), and known deterministic constructions achieve sets of size O(n/eps^3), O(n^2/eps^2), and O((n/eps^2)^{5/4}). Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size O(n/eps^2) with as few random bits as possible. The naive randomized construction requires O(n^2/eps^2) random bits. We give two constructions. The first uses Nisans space-bounded pseudorandom generator to partly derandomize a folklore probabilistic construction of an error-correcting code, and requires O(n log (1/eps)) bits. Our second construction requires O(n log (n/eps)) bits, but is more elementary; it adds randomness to a Legendre symbol construction on Alon, Goldreich, H{aa}stad, and Peralta, and uses Weil sums to bound high moments of the bias.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
Mahaneys Theorem states that, assuming $mathsf{P} eq mathsf{NP}$, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind (Geometric sets of low information content, Theoret. Comp. Sci., 1996). This proof is so simple that it can easily be taught to undergraduates or a general graduate CS audience - not just theorists! - in about 10 minutes, which the author has done successfully several times. We also include applications of Mahaneys Theorem to fundamental questions that bright undergraduates would ask which could be used to fill the remaining hour of a lecture, as well as an application (due to Ikenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theory of the symmetric group and the Geometric Complexity Theory Program. To this author, the fact that sparsity results on NP-complete sets have an application to classical questions in representation theory says that they are not only a gem of classical theoretical computer science, but indeed a gem of mathematics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
