Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization

DOI10.1007/978-3-662-59204-5_12zbMath1452.68089arXiv1901.09423OpenAlexW2914225674MaRDI QIDQ3295273

Avi Wigderson, Orit E. Raz

Publication date: 8 July 2020

Published in: Bolyai Society Mathematical Studies (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.09423

zbMATH Keywords

derandomizationgraph rigiditysymbolic matrix rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Determinants, permanents, traces, other special matrix functions (15A15) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Randomized algorithms (68W20)

Related Items

Connections between graphs and matrix spaces, Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Improved construction for universality of determinant and permanent
• Testing isomorphism of modules.
• Generalized polymatroids and submodular flows
• Matroid matching and some applications
• Maximum rank matrix completion
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Operator scaling: theory and applications
• On graphs and rigidity of plane skeletal structures
• Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits
• Progress on Polynomial Identity Testing-II
• Arithmetic Circuits: A survey of recent results and open questions
• Matroids of gain graphs in applied discrete geometry
• ON THE MAXIMAL RANK IN A SUBSPACE OF MATRICES
• On Generic Rigidity in the Plane
• Conditions for Unique Graph Realizations
• The Rigidity of Graphs
• Generic Rigidity Matroids with Dilworth Truncations
• Bipartite perfect matching is in quasi-NC
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• Systems of distinct representatives and linear algebra
• Derandomizing polynomial identity tests means proving circuit lower bounds