It is shown how the enumeration operators in the "graph model" for lambda-calculus (which can function as a programming language for Recursive Function Theory) can be expanded to allow for "random combinators". The result can then be a model for a new language for random algorithms.
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fourth session of this mini course will take place on Thursday, September 1st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
The material will be in five main parts. We will present an introduction to some ideas in quantum information and foundations, emphasising logical and structural aspects. The aim is to understand how quantum mechanics requires a radical revision to our view of the nature of physical reality, while at the same time opening up new possibilities in the informatic realm. The main emphasis will be the concepts of nonlocality, contextuality and entanglement.
Part 1: Observational Scenarios
Basic notions of contextuality and non-locality. A logical approach to Bell inequalities. Logical forms of contextuality and non-locality, a hierarchy of these notions.
Part 2: Quantum Resources
From bit to qubits. Basic features of finite dimensional quantum mechanics. Quantum realisations of empirical systems. Examples where quantum resources exceed the capabilities of classical systems. The broader world of no-signalling theories.
Part 3: Quantitative Features
Quantifying contextuality, contextuality as a resource for quantum advantage, macroscopic averaging and monogamy of contextuality, classicationof entangled states by degree of non- locality.
The second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 11:00 am – 12:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 11:00 am – 12:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.
Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.
Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.
Theme 3: Query Evaluation and Containment under Alternative Semantics
The second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 1:30 pm – 2:30 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 1:30 pm – 2:30 pm.
Lecture 1: Logic, Probability and Semantics: Introduction and Motivation
Conditional probability as the analogue of logical inference, probabilistic programs as distribution transformers, overview of developments in programming languages for machine learning, probabilistic $\lambda$-
Lecture 2: Background in Measure Theory and Integration
$\Sigma$-algebras, measures, extension theorems, Lebesgue integration, the Radon-Nikodym theorem, conditional expectation on continuous spaces, disintegration.
Lecture 3: The Lawvere-Giry Monad and Probabilistic Relations
The category of measure spaces, probabilistic mappings, the Lawvere-Giry monad, its Kleisli category, Markov kernels, Kozen's semantics for a language with while loops.
Lecture 4: Markov Processes, Bisimulation, and Logical Characterization
Probabilistic bisimulation, the logical characterization of bisimulation; this will include some descriptive set theory: analytic spaces, the unique structure theorem and smooth equivalence relations.
Lecture 5: Metrics for Markov Processes
Metrics between Markov processes, the Kantorovich metric aka the Wasserstein metric, lifting the metric from distributions to processes; metrics from a real-valued modal logic.
The second session of this mini course will take place on Tuesday, August 30th, 2016 3:00 pm – 4:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 3:00 pm – 4:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 3:00 pm – 4:00 pm.
The material will be in five main parts. We will present an introduction to some ideas in quantum information and foundations, emphasising logical and structural aspects. The aim is to understand how quantum mechanics requires a radical revision to our view of the nature of physical reality, while at the same time opening up new possibilities in the informatic realm. The main emphasis will be the concepts of nonlocality, contextuality and entanglement.
Part 1: Observational Scenarios
Basic notions of contextuality and non-locality. A logical approach to Bell inequalities. Logical forms of contextuality and non-locality, a hierarchy of these notions.
Part 2: Quantum Resources
From bit to qubits. Basic features of finite dimensional quantum mechanics. Quantum realisations of empirical systems. Examples where quantum resources exceed the capabilities of classical systems. The broader world of no-signalling theories.
Part 3: Quantitative Features
Quantifying contextuality, contextuality as a resource for quantum advantage, macroscopic averaging and monogamy of contextuality, classicationof entangled states by degree of non- locality.
The first session of this mini course will take place on Monday, August 29th, 2016 1:30 pm – 2:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 11:00 am – 12:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 11:00 am – 12:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fourth session of this mini course will take place on Thursday, September 1st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.
Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.
Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.
Theme 3: Query Evaluation and Containment under Alternative Semantics
The first session of this mini course will take place on Monday, August 29th, 2016 3:00 pm – 4:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 1:30 pm – 2:30 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 1:30 pm – 2:30 pm.
Lecture 1: Logic, Probability and Semantics: Introduction and Motivation
Conditional probability as the analogue of logical inference, probabilistic programs as distribution transformers, overview of developments in programming languages for machine learning, probabilistic $\lambda$-
Lecture 2: Background in Measure Theory and Integration
$\Sigma$-algebras, measures, extension theorems, Lebesgue integration, the Radon-Nikodym theorem, conditional expectation on continuous spaces, disintegration.
Lecture 3: The Lawvere-Giry Monad and Probabilistic Relations
The category of measure spaces, probabilistic mappings, the Lawvere-Giry monad, its Kleisli category, Markov kernels, Kozen's semantics for a language with while loops.
Lecture 4: Markov Processes, Bisimulation, and Logical Characterization
Probabilistic bisimulation, the logical characterization of bisimulation; this will include some descriptive set theory: analytic spaces, the unique structure theorem and smooth equivalence relations.
Lecture 5: Metrics for Markov Processes
Metrics between Markov processes, the Kantorovich metric aka the Wasserstein metric, lifting the metric from distributions to processes; metrics from a real-valued modal logic.
The first session of this mini course will take place on Monday, August 29th, 2016 4:30 pm – 5:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 3:00 pm – 4:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 3:00 pm – 4:00 pm.
Domains arose as the first mathematical models for high-level programming languages. Over time, they have proven to be useful much more broadly, having found applications in mathematics, various areas of computer science, and beyond. Measure theory has played an important role for domains in modeling probabilistic computation. Conversely, domains have provided new insights into measure theory and especially, into probability theory and the theory of stochastic processes. The goal of this talk is to describe the relationship between these areas and how they have interacted. We’ll begin with a brief primer on domains and their basic features. We’ll then consider the traditional domain-theoretic approach to probability measures, namely as valuations. We’ll next describe how the domain-theoretic view of measures and the more traditional functional analytic approach are related. The remainder of the talk will be devoted to describing some of the applications of the domain-theoretic view of measures, including some recent results about domain theory and random variables.
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
The material will be in five main parts. We will present an introduction to some ideas in quantum information and foundations, emphasising logical and structural aspects. The aim is to understand how quantum mechanics requires a radical revision to our view of the nature of physical reality, while at the same time opening up new possibilities in the informatic realm. The main emphasis will be the concepts of nonlocality, contextuality and entanglement.
Part 1: Observational Scenarios
Basic notions of contextuality and non-locality. A logical approach to Bell inequalities. Logical forms of contextuality and non-locality, a hierarchy of these notions.
Part 2: Quantum Resources
From bit to qubits. Basic features of finite dimensional quantum mechanics. Quantum realisations of empirical systems. Examples where quantum resources exceed the capabilities of classical systems. The broader world of no-signalling theories.
Part 3: Quantitative Features
Quantifying contextuality, contextuality as a resource for quantum advantage, macroscopic averaging and monogamy of contextuality, classicationof entangled states by degree of non- locality.
The first session of this mini course will take place on Monday, August 29th, 2016 1:30 pm – 2:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 9:30 am – 10:30 am; the fourth session of this mini course will take place on Thursday, September 1st, 2016 11:00 am – 12:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.
Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.
Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.
Theme 3: Query Evaluation and Containment under Alternative Semantics
The first session of this mini course will take place on Monday, August 29th, 2016 3:00 pm – 4:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 1:30 pm – 2:30 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 1:30 pm – 2:30 pm.
Lecture 1: Logic, Probability and Semantics: Introduction and Motivation
Conditional probability as the analogue of logical inference, probabilistic programs as distribution transformers, overview of developments in programming languages for machine learning, probabilistic $\lambda$-
Lecture 2: Background in Measure Theory and Integration
$\Sigma$-algebras, measures, extension theorems, Lebesgue integration, the Radon-Nikodym theorem, conditional expectation on continuous spaces, disintegration.
Lecture 3: The Lawvere-Giry Monad and Probabilistic Relations
The category of measure spaces, probabilistic mappings, the Lawvere-Giry monad, its Kleisli category, Markov kernels, Kozen's semantics for a language with while loops.
Lecture 4: Markov Processes, Bisimulation, and Logical Characterization
Probabilistic bisimulation, the logical characterization of bisimulation; this will include some descriptive set theory: analytic spaces, the unique structure theorem and smooth equivalence relations.
Lecture 5: Metrics for Markov Processes
Metrics between Markov processes, the Kantorovich metric aka the Wasserstein metric, lifting the metric from distributions to processes; metrics from a real-valued modal logic.
The first session of this mini course will take place on Monday, August 29th, 2016 4:30 pm – 5:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 3:00 pm – 4:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 3:00 pm – 4:00 pm.
The lecture is not related to comedy or satire, given the word "Onion" in the title. It is not a typos either, since it is "onion" and not "anion". The lecture attempts to give a feeling about how physical theories include each other forming an onion-like structure. A deeper understanding of this structure can be obtained by looking at contextuality, and information transmission/processing tasks -- e.g., zero-error information theory, non-local games, computation. Quantum mechanics, which we believe describes quite OK physical reality, appears to be sandwiched between classical mechanics and some exotic physical theories. I will show how this statement can be made quantitative.
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
The material will be in five main parts. We will present an introduction to some ideas in quantum information and foundations, emphasising logical and structural aspects. The aim is to understand how quantum mechanics requires a radical revision to our view of the nature of physical reality, while at the same time opening up new possibilities in the informatic realm. The main emphasis will be the concepts of nonlocality, contextuality and entanglement.
Part 1: Observational Scenarios
Basic notions of contextuality and non-locality. A logical approach to Bell inequalities. Logical forms of contextuality and non-locality, a hierarchy of these notions.
Part 2: Quantum Resources
From bit to qubits. Basic features of finite dimensional quantum mechanics. Quantum realisations of empirical systems. Examples where quantum resources exceed the capabilities of classical systems. The broader world of no-signalling theories.
Part 3: Quantitative Features
Quantifying contextuality, contextuality as a resource for quantum advantage, macroscopic averaging and monogamy of contextuality, classicationof entangled states by degree of non- locality.
The first session of this mini course will take place on Monday, August 29th, 2016 1:30 pm – 2:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 11:00 am – 12:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.
Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.
Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.
Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.
Theme 3: Query Evaluation and Containment under Alternative Semantics
The first session of this mini course will take place on Monday, August 29th, 2016 3:00 pm – 4:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 1:30 pm – 2:30 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 1:30 pm – 2:30 pm.
Lecture 1: Logic, Probability and Semantics: Introduction and Motivation
Conditional probability as the analogue of logical inference, probabilistic programs as distribution transformers, overview of developments in programming languages for machine learning, probabilistic $\lambda$-
Lecture 2: Background in Measure Theory and Integration
$\Sigma$-algebras, measures, extension theorems, Lebesgue integration, the Radon-Nikodym theorem, conditional expectation on continuous spaces, disintegration.
Lecture 3: The Lawvere-Giry Monad and Probabilistic Relations
The category of measure spaces, probabilistic mappings, the Lawvere-Giry monad, its Kleisli category, Markov kernels, Kozen's semantics for a language with while loops.
Lecture 4: Markov Processes, Bisimulation, and Logical Characterization
Probabilistic bisimulation, the logical characterization of bisimulation; this will include some descriptive set theory: analytic spaces, the unique structure theorem and smooth equivalence relations.
Lecture 5: Metrics for Markov Processes
Metrics between Markov processes, the Kantorovich metric aka the Wasserstein metric, lifting the metric from distributions to processes; metrics from a real-valued modal logic.
The first session of this mini course will take place on Monday, August 29th, 2016 4:30 pm – 5:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 3:00 pm – 4:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 3:00 pm – 4:00 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 3:00 pm – 4:00 pm.
In the classical theory of random graphs and structures the properties of interest are typically both uniformly definable and invariant under isomorphisms: connectivity, size and number of components, chromatic number, Hamiltonicity, degree sequence, substructure occurrences and counts, etcetera. It is thus natural to ask, for the different models of random structures, whether the logical complexity it takes to defining such properties has any influence on their asymptotic probability. In this lecture we will start by discussing and proving the first and best known case with a clear and definite answer: the 0-1 law for first-order logic under the uniform probability measure. As we will see, the proof does actually show more and gives also the 0-1 law for several of the fixed-point and infinitary logics at the core of finite model theory. Then we will discuss sparse random graphs and structures, i.e. graphs and structures with a number of edges and tuples that is linear in the number of individual points. Although the theory there is quite different, it still makes sense to study the asymptotic probabilities of logically defined properties. While first-order logic still has a clear and definite answer in this case, fixed-point and infinitary logics are much more challenging and many questions remain open.
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fourth session of this mini course will take place on Thursday, September 1st, 2016 9:30 am – 10:30 am.
The material will be in five main parts. We will present an introduction to some ideas in quantum information and foundations, emphasising logical and structural aspects. The aim is to understand how quantum mechanics requires a radical revision to our view of the nature of physical reality, while at the same time opening up new possibilities in the informatic realm. The main emphasis will be the concepts of nonlocality, contextuality and entanglement.
Part 1: Observational Scenarios
Basic notions of contextuality and non-locality. A logical approach to Bell inequalities. Logical forms of contextuality and non-locality, a hierarchy of these notions.
Part 2: Quantum Resources
From bit to qubits. Basic features of finite dimensional quantum mechanics. Quantum realisations of empirical systems. Examples where quantum resources exceed the capabilities of classical systems. The broader world of no-signalling theories.
Part 3: Quantitative Features
Quantifying contextuality, contextuality as a resource for quantum advantage, macroscopic averaging and monogamy of contextuality, classicationof entangled states by degree of non- locality.
The first session of this mini course will take place on Monday, August 29th, 2016 1:30 pm – 2:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 11:00 am – 12:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 11:00 am – 12:00 pm.
Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.
Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.
Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.
Theme 3: Query Evaluation and Containment under Alternative Semantics
The first session of this mini course will take place on Monday, August 29th, 2016 3:00 pm – 4:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 1:30 pm – 2:30 pm.
Lecture 1: Logic, Probability and Semantics: Introduction and Motivation
Conditional probability as the analogue of logical inference, probabilistic programs as distribution transformers, overview of developments in programming languages for machine learning, probabilistic $\lambda$-
Lecture 2: Background in Measure Theory and Integration
$\Sigma$-algebras, measures, extension theorems, Lebesgue integration, the Radon-Nikodym theorem, conditional expectation on continuous spaces, disintegration.
Lecture 3: The Lawvere-Giry Monad and Probabilistic Relations
The category of measure spaces, probabilistic mappings, the Lawvere-Giry monad, its Kleisli category, Markov kernels, Kozen's semantics for a language with while loops.
Lecture 4: Markov Processes, Bisimulation, and Logical Characterization
Probabilistic bisimulation, the logical characterization of bisimulation; this will include some descriptive set theory: analytic spaces, the unique structure theorem and smooth equivalence relations.
Lecture 5: Metrics for Markov Processes
Metrics between Markov processes, the Kantorovich metric aka the Wasserstein metric, lifting the metric from distributions to processes; metrics from a real-valued modal logic.
The first session of this mini course will take place on Monday, August 29th, 2016 4:30 pm – 5:30 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 3:00 pm – 4:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 3:00 pm – 4:00 pm.
Database transformations (queries, views, mappings) take apart, filter,and recombine source data in order to populate warehouses, materialize views,and provide inputs to analysis tools. As they do so, applications often need to track the relationship between parts and pieces of the sources and parts and pieces of the transformations' output. This relationship is what we call database provenance.
This talk presents an approach to database provenance that relies on two observations. First, provenance is a kind of annotation, and we can develop a general approach to annotation propagation that also covers other applications, for example to uncertainty and access control. In fact, provenance turns out to be the most general kind of such annotation,in a precise and practically useful sense. Second, the propagation of annotation through a broad class of transformations relies on just two operations: one when annotations are jointly used and one when they are used alternatively.This leads to annotations forming a specific algebraic structure, a commutative semiring.
The semiring approach works for annotating tuples, field values and attributes in standard relations, in nested relations (complex values), and for annotating nodes in (unordered) XML. It works for transformations expressed in the positive fragment of relational algebra, nested relational calculus, unordered XQuery, as well as for Datalog, GLAV schema mappings, and tgd constraints. Finally, when properly extended to semimodules it works for queries with aggregates. Specific semirings correspond to earlier approaches to provenance, while others correspond to forms of uncertainty, trust, cost, and access control.
This is joint work with Y. Amsterdamer, D. Deutch, J.N. Foster, T.J. Green, Z. Ives, and G. Karvounarakis.
