Interactions of computational complexity theory and mathematics
From MaRDI portal
Publication:6198725
DOI10.4171/icm2022/190arXiv1710.09780OpenAlexW2766507469MaRDI QIDQ6198725
Publication date: 20 March 2024
Published in: International Congress of Mathematicians (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.09780
Cites Work
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing
- The Paulsen problem, continuous operator scaling, and smoothed analysis
- Space-efficient Gröbner basis computation without degree bounds
- Computational Complexity
- Geometry and Complexity Theory
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Euclidean distortion and the sparsest cut
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- On Matrices Whose Real Linear Combinations are Nonsingular
- Systems of distinct representatives and linear algebra
- Extracting Randomness Using Few Independent Sources
- On the solution‐space geometry of random constraint satisfaction problems
- Expander flows, geometric embeddings and graph partitioning
- Algorithms in invariant theory
- Computational Complexity
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Vector fields on spheres
- Noise sensitivity of Boolean functions and applications to percolation
- Semi-invariants of quivers as determinants
- Semi-invariants of quivers for arbitrary dimension vectors
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computational invariant theory. With two appendices by Vladimir L. Popov and an addendum by Nobert A. Campo and Vladimir L. Popov
- On distinguishing prime numbers from composite numbers
- The complexity of computing the permanent
- The product replacement prospector.
- Extremal problems in discrete geometry
- Invariants and the ring of generic matrices
- The coarse geometric Novikov conjecture and uniform convexity
- Lifts, discrepancy and nearly optimal spectral gap
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- A reinforcement of property (T)
- Testing isomorphism of modules.
- Noise stability of functions with low influences: invariance and optimality
- Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
- Generating random elements in finite groups.
- Random generation of combinatorial structures from a uniform distribution
- Vector spaces of matrices of low rank
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Ramanujan graphs
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Probabilistic algorithm for testing primality
- Factoring polynomials with rational coefficients
- Primality testing and Abelian varieties over finite fields
- Invariants of several matrices
- The invariant theory of \(n\times n\) matrices
- Riemann's hypothesis and tests for primality
- Semidefinite programming in combinatorial optimization
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- An elementary proof of the restricted invertibility theorem
- PRIMES is in P
- A sum-product estimate in finite fields, and applications
- The geometry of graphs and some of its algorithmic applications
- Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
- The Paulsen problem made simple
- Algorithms for orbit closure separation for invariants and semi-invariants of matrices
- Nonlinear spectral calculus and super-expanders
- Theory of monomer-dimer systems
- Unzerlegbare Darstellungen. I. (Indecomposable representations. I)
- Measured descent: A new embedding method for finite metrics
- Sur une généralisation du groupe orthogonal à quatre variables
- A Decade of Lattice Cryptography
- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
- Counting independent sets up to the tree threshold
- On P vs. NP and geometric complexity theory
- Integer Programming with a Fixed Number of Variables
- On the size of Kakeya sets in finite fields
- Arithmetic Circuits: A survey of recent results and open questions
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- A Counterexample to Strong Parallel Repetition
- Spectral Sparsification of Graphs
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
- Extensions of Pure States
- Geometric bounds on the Ornstein-Uhlenbeck velocity process
- Disproof of the Mertens conjecture.
- ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
- Primality and identity testing via Chinese remaindering
- Expander graphs and their applications
- A constructive proof of the general lovász local lemma
- On the power of unique 2-prover 1-round games
- Extractors
- Relative bilinear complexity and matrix multiplication.
- The Knowledge Complexity of Interactive Proof Systems
- TRACE IDENTITIES OF FULL MATRIX ALGEBRAS OVER A FIELD OF CHARACTERISTIC ZERO
- A Fast Monte-Carlo Test for Primality
- A random polynomial-time algorithm for approximating the volume of convex bodies
- A Parallel Repetition Theorem
- Mathematics and Computation
- Mixing in time and space for lattice spin systems: A combinatorial view
- It is easy to determine whether a given integer is prime
- Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
- Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
- Invariant Theory and Scaling Algorithms for Maximum Likelihood Estimation
- Maximum Likelihood Estimation for Matrix Normal Models via Quiver Representations
- Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
- Knapsack Public Key Cryptosystems and Diophantine Approximation
- HIGH DIMENSIONAL EXPANDERS
- Twice-Ramanujan Sparsifiers
- Analysis of Boolean Functions
- Fractional Sylvester–Gallai theorems
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Fully homomorphic encryption using ideal lattices
- A constructive proof of the Lovász local lemma
- Selected Applications of LLL in Number Theory
