Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFooling Polytopes
314
0
0.0
(
0
)
Added by
Li-Yang Tan
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give a pseudorandom generator that fools $m$-facet polytopes over ${0,1}^n$ with seed length $mathrm{polylog}(m) cdot log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any ${0,1}$-integer program.
rate research
Read More
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
We give a pseudorandom generator that fools degree-$d$ polynomial threshold functions over $n$-dimensional Gaussian space with seed length $mathrm{poly}(d)cdot log n$. All previous generators had a seed length with at least a $2^d$ dependence on $d$. The key new ingredient is a Local Hyperconcentration Theorem, which shows that every degree-$d$ Gaussian polynomial is hyperconcentrated almost everywhere at scale $d^{-O(1)}$.
We study the complexity of computing the projection of an arbitrary $d$-polytope along $k$ orthogonal vectors for various input and output forms. We show that if $d$ and $k$ are part of the input (i.e. not a constant) and we are interested in output-sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are in some sense non-degenerate. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable linear subspace and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. To compare the complexity of projection and vertex enumeration, we define new complexity classes based on the complexity of Vertex Enumeration.
A biconvex polytope is a convex polytope that is also tropically convex. It is well known that every bounded cell of a tropical linear space is a biconvex polytope, but its converse has been a conjecture. We classify biconvex polytopes, and prove the conjecture by constructing a matroid subdivision dual to a biconvex polytope. In particular, we construct matroids from bipartite graphs, and establish the relationship between bipartite graphs and faces of a biconvex polytope. We also show that there is a bijection between monomials and a maximal set of vertices of a biconvex polytope.
It is an amazing and a bit counter-intuitive discovery by Micha Perles from the sixties that there are ``non-rational polytopes: combinatorial types of convex polytopes that cannot be realized with rational vertex coordinates. We describe a simple construction of non-rational polytopes that does not need duality (Perles ``Gale diagrams): It starts from a non-rational point configuration in the plane, and proceeds with so-called Lawrence extensions. We also show that there are non-rational polyhedral surfaces in 3-space, a discovery by Ulrich Brehm from 1997. His construction also starts from any non-rational point configuration in the plane, and then performs what one should call Brehm extensions, in order to obtain non-rational partial surfaces. These examples and objects are first mile stones on the way to the remarkable universality theorems for polytopes and for polyhedral surfaces by Mnev (1986), Richter-Gebert (1994), and Brehm (1997).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
