Noncommutative constraint satisfaction problems

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=oqQfQ4smdZk


Duration: 18:38
238 views
6

Hamoon Mousavi (Simons Institute)
https://simons.berkeley.edu/talks/hamoon-mousavi-simons-institute-2023-09-08
Meet the Fellows Welcome Event Fall 2023

In this short talk we motivate the study of noncommutative constraint satisfaction problems. Constraint satisfaction problems from theoretical computer science have a natural framing as optimization of polynomials in commuting variables. Noncommutativity is one of the defining features of quantum mechanics. So it is not surprising that noncommutative polynomial optimization plays an important role in quantum computer science. At a first glance it seems that noncommutative polynomial optimization must be more complex. However this is not always true for example when the polynomial is coming from certain constraint satisfaction problems ...



Other Videos By Simons Institute for the Theory of Computing


2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI
2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works
2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent
2023-09-08Quantum Cryptography in Algorithmica
2023-09-08Noncommutative constraint satisfaction problems
2023-09-08Faster inverse maintenance for faster conic programming
2023-09-08Unifying strongly polynomial algorithms for subclasses of Linear Programs
2023-09-08Fast sparsification via convex optimization and chaining
2023-09-08Practical Graph Algorithms: Scalability and Privacy
2023-09-08Recent advances in vertex connectivity
2023-09-08Shortest paths, dynamic algorithms, and fine-grained complexity
2023-09-08Recent Trends in Minimum Cut Algorithms
2023-09-05Introduction to Data Structures and Optimization for Fast Algorithms
2023-09-01Optimization: Interior Point Methods Part 2
2023-09-01Optimization: Interior Point Methods Part 1


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2023
Hamoon Mousavi