{Symmetry, Logic, Computation}

# click the upper-left icon to select videos from the playlist

source: Simons Institute    2016年11月7日
{Symmetry, Logic, Computation}
Many aspects of logical structure in computation involve the study of symmetry in some form, and this study often deploys algebraic tools, such as permutation groups. In descriptive complexity theory and in database theory, the study of symmetry underlies results about the expressive power of order-invariant query languages. The study of symmetries has also played a key role in advancing the understanding of the tractability frontier in constraint satisfaction problems. Recent work in automata with an infinite alphabet (factored by a suitable symmetry) has tied into work in semantics dealing with nominal computation. This workshop will focus on exposing the common methods underlying various studies of symmetry in logic computation and also in related areas, such as symmetry in quantum information and the complexity of the graph isomorphism problem.
For more information, please visit https://simons.berkeley.edu/workshops/logic2016-2.
These presentations were supported in part by an award from the Simons Foundation.

Orbit-Finite Sets 1:07:25 Mikolaj Bojanczyk, University of Warsaw https://simons.berkeley.edu/talks/mik...
The Power of Two Variables 25:29
Towards Capturing Order-Independent P 30:53
New Results on Register Automata 30:52
Simulation and Bisimulations for Probabilistic Systems, and their Logical Contents 28:24
Operations on Languages and Codensity Monads 35:26
Fibred Categories of Tree Automata 31:26
Pro-Aperiodic Monoids via Saturated Models 28:05
Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic 55:19
A Dichotomy Structure Theorem for the Resilience Problem 28:16
Symmetric Circuits and Fixed-Point Logics 35:45
One Eilenberg Theorem to Rule Them All 28:11
A Finite Alternation Result for Reversible Boolean Circuits 31:40
Graph Isomorphism Via Non-Local Games 29:43
Extending Symmetric Circuits 22:55
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps 21:32
{Symmetry, Logic, Constraint Satisfaction Problem} 54:11
Combinatorial Properties of the Weisfeiler-Leman Algorithm 29:35
Approximating Graph Isomorphism through Linear Maps 31:29
Power and Limits of LP and SDP Relaxations 28:57
Reducts of Finitely Bounded Homogeneous Structures, and... 28:33
Braid Groups, Hecke Algebras, Representations, and Anyons 41:38
FO-Definable Constraint Satisfaction Problems 26:36
Functional Programming Over Sets with Atoms 31:40
Logic and Bisimulation for Guarded Teams 35:19
Logic in Computer Science, Engineering and Industry 33:36
Symmetry-Preserving Finite Synthesis and Amalgamation 34:53
Near-Optimal Expanding Generating Sets for Solvable Permutation Groups 17:46
Testing Assignments to Constraint Satisfaction Problems 30:36
The Expressiveness of Recognizability by Orbite Finite Nominal Monoids 31:15
The Logic of Counting Query Answers 28:26