Symmetry, Logic, Computation 2016
2016-11-07..2016-11-10
Berkeley, United States
who it's for
finite model theorists, automata theorists, complexity theorists, constraint satisfaction researchers, category theorists, algebraists in semigroup theory, nominal programming researchers, logic in computer science researchers
topics
orbit-finite nominal sets; first-order two-variable fragment over words; register automata decidability; bisimulation for probabilistic systems; Stone duality for recognizers; pro-aperiodic monoids and omega-terms; Weisfeiler-Leman algorithm analysis; symmetric circuits and FPC; subgraph isomorphism lower bounds; CFI construction and FPC limits; codensity monads and Eilenberg theorems; functional programming over sets with atoms
| title | author | length |
|---|---|---|
| Orbit-Finite Sets | Mikołaj Bojańczyk | 01h 07m |
Claims an equivalence between the syntactic notion definable sets (finite set‑builder expressions over a fixed atom structure) and the semantic notion… | ||
| The Power of Two Variables | Howard Straubing | 25m |
First-order logic with two variables over words is exactly captured by an algebraic condition on the syntactic monoid: definability is decidable by checking… | ||
| Towards Capturing Order-Independent P | Neil Immerman | 31m |
Asks whether all polynomial-time graph properties that ignore vertex order—order-independent P—have a clean logical description. Gives the concrete negative… | ||
| New Results on Register Automata | Andrzej S. Murawski | 31m |
Shows concrete complexity and decidability boundaries for automata over infinite alphabets: emptiness reduces to a finite-alphabet reachability via an r+1 name… | ||
| Simulation and Bisimulations for Probabilistic Systems, and their Logical Contents | Nathanaël Fijalkow | 28m |
Defines models (labeled Markov chains, labeled MDPs with convex choices) and works on equivalence of the induced probability functions. Shows equality of two… | ||
| Operations on Languages and Codensity Monads | Daniela Petrisan | 35m |
Presents a concrete duality route from languages to recognizers: use Stone duality to turn the Boolean algebra of quotients into a Stone space with a dense… | ||
| Fibred Categories of Tree Automata | Colin Riba | 31m |
Builds a category whose objects are tree automata and morphisms = strategies in the acceptance games and shows concrete constructions: product and unit… | ||
| Pro-Aperiodic Monoids via Saturated Models | Sam Van Gool | 28m |
Free pro-aperiodic monoids are realized as the Stone dual of the Lindenbaum algebra for first-order theory of finite words, and elements are represented by… | ||
| Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic | Benjamin Rossman | 55m |
States that colored Subgraph Isomorphism has nearly tight AC0 circuit lower bounds — circuits need n^{Ω(treewidth / log treewidth)} — and AC0 formulas require… | ||
| A Dichotomy Structure Theorem for the Resilience Problem | Cibele Freire | 28m |
Classifies resilience for self‑join‑free conjunctive queries: if the hypergraph of the closed query Q contains a triad then computing the minimum contingency… | ||
| Symmetric Circuits and Fixed-Point Logics | Matthew Anderson | 36m |
Characterizes exactly which graph properties symmetric circuits capture: polynomial-size symmetric circuits without majority correspond to fixed-point logic… | ||
| One Eilenberg Theorem to Rule Them All | Stefan Milius | 28m |
Claim: a single, general Eilenberg-style theorem that unifies more than a dozen prior correspondences and produces new instances (infinite words, weighted… | ||
| A Finite Alternation Result for Reversible Boolean Circuits | Peter Selinger | 32m |
For n ≥ 4 every even reversible Boolean function on n bits decomposes as a composition of at most nine reversible maps that each act on n−1 bits, with a proved… | ||
| Graph Isomorphism Via Non-Local Games | Simone Severini | 30m |
Defines quantum isomorphism by an N by N block matrix whose blocks are orthogonal projectors satisfying (A_G ⊗ I_d) P = P (A_H ⊗ I_d) and shows a perfect… | ||
| Extending Symmetric Circuits | Gregory Wilsenach | 23m |
Extends Anderson and Daw’s circuit model and proves a support theorem showing every gate in a P-uniform symmetric circuit with matrix-symmetric gates has… | ||
| Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps | Christoph Berkholz | 22m |
Proves that for every k there exist n‑vertex relational structures that are k‑variable distinguishable but require quantifier rank at least n^{Ω(k / log k)}… | ||
| {Symmetry, Logic, Constraint Satisfaction Problem} | Libor Barto | 54m |
Fixed-template finite-domain CSPs are hard exactly when they lack the right algebraic symmetries: existence of a nontrivial polymorphism clone (equivalently… | ||
| Combinatorial Properties of the Weisfeiler-Leman Algorithm | Sandra Kiefer | 30m |
Proves a full combinatorial classification: a graph is identified by 1-dimensional Weisfeiler-Leman exactly if it flips to a bouquet forest, and this yields a… | ||
| Approximating Graph Isomorphism through Linear Maps | Anuj Dawar | 31m |
Defines a family of partition‑refinement equivalences parameterized by K, L and a set of primes Omega that refine k‑dimensional Weisfeiler‑Leman by using ranks… | ||
| Power and Limits of LP and SDP Relaxations | Stanislav Zivny | 29m |
For any finite valued-CSP language the result gives a precise dichotomy: if the language’s fractional polymorphism support satisfies the bounded width… | ||
| Reducts of Finitely Bounded Homogeneous Structures, and... | Antoine Mottet | 29m |
Claims a conditional P versus NP-complete dichotomy for reducts of finitely bounded homogeneous structures assuming the finite-domain tractability conjecture… | ||
| Braid Groups, Hecke Algebras, Representations, and Anyons | Andreas Blass | 42m |
Fibonacci anyons implement qubits: three anyons fusing to one give a two‑dimensional Hilbert space and braiding those anyons generates a dense subgroup of… | ||
| FO-Definable Constraint Satisfaction Problems | Joanna Ochremiak | 27m |
Decision: for any finite template T, satisfiability of FO-definable instances over atoms with equality is decidable (via orbit-constant homomorphisms); key… | ||
| Functional Programming Over Sets with Atoms | Bartek Klin | 32m |
A Haskell library called n Lambda implements definable (orbit‑finite) sets with atoms by representing values as first‑order formulas and bound/free‑variable… | ||
| Logic and Bisimulation for Guarded Teams | Erich Grädel | 35m |
Introduces guarded teams and proves characterization theorems: properties definable in team semantics that are invariant under guarded bisimulation correspond… | ||
| Logic in Computer Science, Engineering and Industry | Yuri Gurevich | 34m |
Survey links classical logic results to concrete engineering: types powering modern languages and Java/.NET virtual machines; deterministic pushdown parsing… | ||
| Symmetry-Preserving Finite Synthesis and Amalgamation | Martin Otto | 35m |
Claims a concrete construction of finite groupoids avoiding coset cycles up to any fixed n and uses them to produce symmetry-preserving finite realizations of… | ||
| Near-Optimal Expanding Generating Sets for Solvable Permutation Groups | Prajakta Nimbhorkar | 18m |
Constructs explicit expanding generating sets for solvable subgroups of S_n by using the group’s derived series to reduce to abelian quotients, lifting… | ||
| Testing Assignments to Constraint Satisfaction Problems | Matt Valeriote | 31m |
Gives a precise criterion: CSP assignments admit constant-query testing exactly when the template’s polymorphism algebra has both a majority and a Maltsev (or… | ||
| The Expressiveness of Recognizability by Orbite Finite Nominal Monoids | Thomas Colcombet | 31m |
Claim: monadic second-order logic with rigid guards exactly captures languages recognisable by orbit-finite nominal monoids, and the first-order fragment… | ||
| The Logic of Counting Query Answers | Hubie Chen | 28m |
A logic called sharp logic is defined that outputs a numeric value for a formula on a finite structure and supports casting first‑order formulas, projection… | ||
| nothing matches | ||