1 - 4 of 4 articles
In this paper we study the algorithmic complexity of the following problems:(1)Given a vertex-colored graph X = (V,E,c), compute a minimum cardinality set of vertices S⊆ V such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S...
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝd that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e.,...
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best-known lower and upper bounds on its complexity. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well. We bridge the gap for...
We show that there is an equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field 𝔽, there is a non-zero n2-variate polynomial P ε 𝔽[x1, 1, ..., xn, n] of degree at most poly(n) such that every matrix M...
Read and print from thousands of top scholarly journals.
Continue with Facebook
Log in with Microsoft
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Sign Up Log In
To subscribe to email alerts, please log in first, or sign up for a DeepDyve account if you don’t already have one.
To get new article updates from a journal on your personalized homepage, please log in first, or sign up for a DeepDyve account if you don’t already have one.