We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP. This is the first nontrivial result on the computational complexity of this problem, which naively amounts to a quadratically constrained program. Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard, in general [C. Ikenmeyer, K. D. Mulmuley, and M. Walter, preprint, arXiv:1507.02955, 2015]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem.

One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = !VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that !VP is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP subseteq Newton-VP subseteq VP* subseteq VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP. Although we do not yet construct explicit candidates for the polynomial families in !VP\VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \VP based on semi-invariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic varieties, the problem that lies at the heart of the foundational classification problem of algebraic geometry. Specifically: (1) It is shown that in characteristic zero black-box derandomization of PIT for diagonal depth three circuits brings the problem of derandomizing Noether's Normalization Lemma, for the ring of invariants of any explicit linear action of a classical algebraic group of constant dimension, from EXPSPACE (where it is currently) to P. Next it is shown that assuming the Generalized Riemann Hypothesis (GRH), instead of the black-box derandomization hypothesis, brings the problem from EXPSPACE to quasi-PH, instead of P. Thus black-box derandomization of diagonal depth three circuits takes us farther than GRH here on the basis of the current knowledge. Variants of the main implication are also shown assuming, instead of the black-box derandomization hypothesis in characteristic zero, Boolean lower bounds for constant-depth threshold circuits or uniform Boolean conjectures, in conjunction with GRH. These results may explain in a unified way why proving lower bounds or derandomization results for constant-depth arithmetic circuits in characteristic zero or constant-depth Boolean threshold circuits, or proving uniform Boolean conjectures without relativizable proofs has turned out to be so hard, and also why GRH has turned out to be so hard from the complexity-theoretic perspective. Thus this investigation reveals that the foundational problems of Geometry (classification and GRH) and Complexity Theory (lower bounds and derandomization) share a common root difficulty that lies at the junction of these two fields. We refer to it as the GCT chasm. (2) It is shown that black-box derandomization of PIT in a strengthened form implies derandomization of Noether's Normalization Lemma in a strict form for any explicit algebraic variety. (3) Conversely, it is shown that derandomization of Noether's Normalization Lemma in a strict form for specific explicit varieties implies this strengthened form of black box derandomization of PIT and its various variants. (4) A unified geometric complexity theory (GCT) approach to derandomization and classification is formulated on the basis of this equivalence.

This article gives an overview of the geometric complexity theory (GCT) approach towards the P vs. NP and related problems focusing on its main complexity theoretic results. These are: (1) two concrete lower bounds, which are currently the best known lower bounds in the context of the P vs. NC and permanent vs. determinant problems, (2) the Flip Theorem, which formalizes the self-referential paradox in the P vs. NP problem, and (3) the Decomposition Theorem, which decomposes the arithmetic P vs. NP and permanent vs. determinant problems into subproblems without self-referential difficulty, consisting of positivity hypotheses in algebraic geometry and representation theory and easier hardness hypotheses.

In [K. D. Mulmuley and M. Sohoni, SIAM J. Comput., 31 (2001), pp. 496–526], henceforth referred to as Part I, we suggested an approach to the P vs. $NP$ and related lower bound problems in complexity theory through geometric invariant theory. In particular, it reduces the arithmetic (characteristic zero) version of the $NP \not \subseteq P$ conjecture to the problem of showing that a variety associated with the complexity class $NP$ cannot be embedded in a variety associated with the complexity class P. We shall call these class varieties associated with the complexity classes P and $NP$. This paper develops this approach further, reducing these lower bound problems—which are all nonexistence problems—to some existence problems: specifically to proving the existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel–Weil theorem to a class of orbit closures, which include class varieties. The second result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class $NC$. These results indicate that the fundamental lower bound problems in complexity theory are, in turn, intimately linked with explicit construction problems in algebraic geometry and representation theory. The results here were announced in [K. D. Mulmuley and M. Sohoni, in Advances in Algebra and Geometry (Hyderabad, $2001$), Hindustan Book Agency, New Delhi, India, 2003, pp. 239–261].

We suggest an approach based on geometric invariant theory to the fundamental lower bound problems in complexity theory concerning formula and circuit size. Specifically, we introduce the notion of a partially stable point in a reductive-group representation, which generalizes the notion of stability in geometric invariant theory due to Mumford [Geometric Invariant Theory, Springer-Verlag, Berlin, 1965]. Then we reduce fundamental lower bound problems in complexity theory to problems concerning infinitesimal neighborhoods of the orbits of partially stable points. We also suggest an approach to tackle the latter class of problems via construction of explicit obstructions.

We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using poly(n) processors even when the bit-lengths of the weights on the edges are restricted to be of size O(log/sup 3/ n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in the unbounded fan-in PRAM model without bit operations.

We define a natural and realistic model of parallel computation called the PRAM model without bit operations. It is like the usual PRAM model, the main difference being that no bit operations are provided. It encompasses virtually all known parallel algorithms for (weighted) combinatorial optimization and algebraic problems. In this model we prove that for some large enough constant b, the mincost-flow problem for graphs with n vertices cannot be solved deterministically (or with randomization) in $\sqrt n /b$ (expected) time using $2^{\sqrt {n}/b}$ processors; this is so even if we restrict every cost and capacity to be an integer (nonnegative if it is a capacity) of bitlength at most an for some large enough constant a. A similar lower bound is also proved for the max-flow problem. It follows that these problems cannot be solved in our model deterministically (or with randomization) in $\Omega(N^{c})$ (expected) time with $2^{\Omega(N^{c})}$ processors, where c is an appropriate positive constant and N is the total bitlength of the input. Since these problems were known to be P-complete, this provides concrete support for the belief that P-completeness implies high parallel complexity and for the $P\not = NC$ conjecture. Our lower bounds also extend to the PRAM model with limited bit operations, which provides instructions for parity and left or right shift by one bit. Our proof is based on basic algebraic geometry. So we investigate if the algebrogeometric approach could also work for the P versus NC problem. Our results support this possibility, and a close analysis of the limitation of our technique in this context suggests that such a proof of $P \not = NC$ should somehow use geometric invariant theory in a deep way.

We continue our study [27] of lower bounds on par-aHel complexity via an algebraic approach.First, we give a further application of our general lower bound [27] on parallel complexity of a general optimization problem in the PRAM model without bit operations.We show that, for some large enough constant b, the s-t-mincut problem for weighted undirected graphs with n vertices cannot be solved in this model, deterministically or with randomization, within &/b time using 2@/b processors; this is so even if we restrict every edge-capacity to be a nonnegative integer of bitlength at most anz for some large enough constant a. Parallel complexity of this problem was wide open.It was neither known to be P-complete nor was it known to be in (R) NC; we believe our approach may be used to study parallel complexity of many such problems.Second, and most important, we examine the bearing of our lower bounds and techniques on the P # NC conjecture, and in particular, on the possibility of an algebraic proof for it.It turns out that our techniques are insufficient in this regard because they have a fundamental limitation.But a closer analysis of this limitation also suggests what an algebraic proof of P # NC ought to exploit: it should somehow use properties of determinantal or similar rings and varieties in a deep way.This, in conjunction with our lower bounds in a restricted, yet realistic PRAM model, suggests that the algebraic approach, though seemingly quite hard, may be a right one for this problem.

It is shown that

In this note, we generalize the h-vector for simple, bounded convex polytopes [14] to the h-matrix for simple, bounded k-complexes. We observe that the h-matrix is invariant with respect to the defining linear function, and that the Dehn-Sommerville relations and McMullen's Upper Bound Theorem [13] for convex polytopes follow from the invariance ofthe 0-th row and column of this matrix. The invariance of the other entries in the h-matrix should, perhaps, be investigated more. One new consequence is that, given any non-degenerate linear function z, the number of local z-minima on the lth level of any d-dimensional arrangement is bounded by (l+d-1 / d-1) with exact equality if the l-th level is bounded and simple.

The so called randomized incremental algorithms in computational geometry can be thought of as a generalization of Quicksort to higher dimensional geometric problems. They all construct the geometric complex in the given problem, such as a Voronoi diagram or a convex polytope, by adding the objects in the input set, one at a time, in a random order. The author shows that the expected running times of most of the randomized incremental algorithms in computational geometry do not change (up to a constant factor), when the sequence of additions is not truly random but is instead generated using only O(log n) random bits. The pseudo-random generator used is a generalization of the well known linear congruential generator.>

We generalize the classical Dehn-Sommerville relations for simple, convex polytopes to compact, transverse intersections of arbitrary smooth manifolds with boundaries.

Article Free Access Share on Randomized multidimensional search trees (extended abstract): dynamic sampling Author: Ketan Mulmuley The University of Chicago The University of ChicagoView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 121–131https://doi.org/10.1145/109648.109662Published:01 June 1991Publication History 25citation438DownloadsMetricsTotal Citations25Total Downloads438Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present algorithms for maintaining data structures supporting fast point location queries in arrangements of hyperplanes with dimension less than or equal to four.This data structure allows for ity which is likely to have further applications to other dynamic algorithms.

A randomized technique, called dynamic shuffling, is given for multidimensional dynamic search. This technique, when specialized to the problem of searching in sorted lists, yields the previously known randomized binary trees (treaps). The crux of the technique is a multidimensional generalization of the rotation operation on binary search trees. Simultaneously, it is shown how to dynamize the randomized incremental algorithms so as to allow additions as well as deletions of objects. The techniques are based on remembering the history of the actual or imaginary sequence of updates. The techniques are applied to several problems in computational geometry.>

The use of randomization in dynamic search structures by means of a technique called dynamic sampling is investigated. In particular, an efficient algorithm for dynamic (logarithmic time) point location in 3-D partitions induced by a set of possibly interesting polygons in R/sup 3/ is given. The expected running time of the algorithm on a random sequence of updates is close to optimal. Efficient algorithms for dynamic nearest-k-neighbor queries and half space range queries in R/sup d/ are also given.>

Article Hidden surface removal with respect to a moving view point Share on Author: Ketan Mulmuley The Univ. of Chicago, Chicago, IL The Univ. of Chicago, Chicago, ILView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 512–522https://doi.org/10.1145/103418.103471Online:03 January 1991Publication History 18citation354DownloadsMetricsTotal Citations18Total Downloads354Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Randomized, optimal algorithms to find a partition of the plane induced by a set of algebraic segments of a bounded degree, and a set of linear chains of a bounded degree, are given. This paper also provides a new technique for clipping, called virtual clipping , whose overhead per window W depends logarithmically on the number if intersections between the borders of W and the input segments. In contrast, the overhead of the conventional clipping technique depends linearly on this number of intersections. As an application of virtual clipping, a new simple and efficient algorithm for plannar point location is given.

We give efficient, output sensitive algorithms to construct levels of order 1 to k in a nonredundant arrangement of hyperplanes in R d, and Voronoi diagrams of order to 1 to k of a given collection of sites in R d.

guaranteed to be 0(n).Contrast this with the O(n3/') worst,

108 Efficient, randomized algorithms are given for the following problems: (1) construction of levels of order 1 to k in an arrangement of hyperplanes in any dimension; (2) construction of higher order Voronoi diagrams of order 1 to k in any dimension; (3) hidden surface removal for completely general scenes (intersecting and curved faces are allowed). A combinatorial tool in the form of a mathematical series called a theta series is associated with a configuration of polytopes in R/sup d/. It is used to study the combinatorial, as well as algorithmic, complexity of the geometric problems under consideration.>

We give an efficient, randomized hidden surface removal algorithm, with the best time complexity so far. A distinguishing feature of this algorithm is that the expected time spent by this algorithm on junctions which are at the "obstruction level" l, with respect to the viewer, is inversely proportional to l. This provably holds for any input, regardless of the way in which faces are located in the scene, because the expectation is with respect to randomization in the algorithm, and does not depend on the input. In practice, this means that the time complexity is roughly proportional to the size of the actually visible output times logarithm of the average depth complexity of the scene (this logarithm is very small generally).

A fast randomized algorithm is given for finding a partition of the plane induced by a given set of linear segments. The algorithm is ideally suited for a practical use because it is extremely simple and robust, as well as optimal; its expected running time is O(m+n log n) where n is the number of input segments and m is the number of points of intersection. The storage requirement is O(m+n). Though the algorithm itself is simple, the global evolution of the partition is complex, which makes the analysis of the algorithm theoretically interesting in its own right.>

A new algorithm for finding a maximum matching in a general graph is presented; its special feature being that the only computationally non-trivial step required in its execution is the inversion of a single integer matrix.Since this step can be parallelized, we get a simple parallel (RNC2) algorithm.At the heart of our algorithm lies a probabilistic lemma, the isolating lemma.We show applications of this lemma to parallel computation and randomized reductions.

No abstract available.

Full abstraction is a well known issue in denotational semantics. For a special case of typed lambda calculus, PCF, Plotkin showed that the classical model consisting of domains of continuous functions is not fully abstract. Milner constructed a fully abstract model of typed lambda calculus syntactically. However, its precise relationship with the classical model was not clear, and hence it remained open whether a fully abstract model can be constructed which is related to the classical model in a pleasant way. In this paper we show that a fully abstract, extensional model of typed lambda calculus can be constructed as a homomorphic retraction of the classical model.