Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Computing the Shadows and Slices of Polytopes
210
0
0.0
(
0
)
Added by
Hans Raj Tiwary
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Hans Raj Tiwary
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
It is well known that any graph admits a crossing-free straight-line drawing in $mathbb{R}^3$ and that any planar graph admits the same even in $mathbb{R}^2$. For a graph $G$ and $d in {2,3}$, let $rho^1_d(G)$ denote the minimum number of lines in $mathbb{R}^d$ that together can cover all edges of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. - For $din{2,3}$, we prove that deciding whether $rho^1_d(G)le k$ for a given graph $G$ and integer $k$ is ${existsmathbb{R}}$-complete. - Since $mathrm{NP}subseteq{existsmathbb{R}}$, deciding $rho^1_d(G)le k$ is NP-hard for $din{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${existsmathbb{R}}subseteqmathrm{PSPACE}$, both $rho^1_2(G)$ and $rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $rho^1_2$ or $rho^1_3$ sometimes require irrational coordinates. - Let $rho^2_3(G)$ be the minimum number of planes in $mathbb{R}^3$ needed to cover a straight-line drawing of a graph $G$. We prove that deciding whether $rho^2_3(G)le k$ is NP-hard for any fixed $k ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $mathrm{P}=mathrm{NP}$.
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.
We study the combinatorial Reeb flow on the boundary of a four-dimensional convex polytope. We establish a correspondence between combinatorial Reeb orbits for a polytope, and ordinary Reeb orbits for a smoothing of the polytope, respecting action and Conley-Zehnder index. One can then use a computer to find all combinatorial Reeb orbits up to a given action and Conley-Zehnder index. We present some results of experiments testing Viterbos conjecture and related conjectures. In particular, we have found some new examples of polytopes with systolic ratio $1$.
The disjointness problem - where Alice and Bob are given two subsets of ${1, dots, n}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $Theta(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik-Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. In this paper, we construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $widetilde{Theta}left(dlog left( n/d right)right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Thetaleft( dlog left( n/d right) right)$, and this is tight among all set systems of VC dimension $d$.
This paper establishes some of the fundamental barriers in the theory of computations and finally settles the long-standing computational spectral problem. That is to determine the existence of algorithms that can compute spectra $mathrm{sp}(A)$ of classes of bounded operators $A = {a_{ij}}_{i,j in mathbb{N}} in mathcal{B}(l^2(mathbb{N}))$, given the matrix elements ${a_{ij}}_{i,j in mathbb{N}}$, that are sharp in the sense that they achieve the boundary of what a digital computer can achieve. Similarly, for a Schrodinger operator $H = -Delta+V$, determine the existence of algorithms that can compute the spectrum $mathrm{sp}(H)$ given point samples of the potential function $V$. In order to solve these problems, we establish the Solvability Complexity Index (SCI) hierarchy and provide a collection of new algorithms that allow for problems that were previously out of reach. The SCI is the smallest number of limits needed in the computation, yielding a classification hierarchy for all types of problems in computational mathematics that determines the boundaries of what computers can achieve in scientific computing. In addition, the SCI hierarchy provides classifications of computational problems that can be used in computer-assisted proofs. The SCI hierarchy captures many key computational issues in the history of mathematics including the insolvability of the quintic, Smales problem on the existence of iterative generally convergent algorithm for polynomial root finding, the computational spectral problem, inverse problems, optimisation etc.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
