UNIBZ KRDB Internal Seminars

A tutorial 0on PCP theorem

2005-10-09T04:06:00.000-07:00

Date Thursday, October 20, 5:20-7:30 pm
the first tutorial of

5-hour tutorial
"PCP theorem, Interactive Proofs and Inapproximability of
Optimization Problems"

This talk would be more a tutorial, then a seminar. Full proofs, explanations and background materials will be given. I have given it once already in UoQ and this tutorial is quite ready in sense of quality of presentation.

PCP theorem is considered to be one of the major development in TCS in 90s. Perhaps, since 1992 every STOC and FOCS conference has at least one article strongly related to the PCP theorem.

Basically the PCP theorem provides a new characterization of NP class as a class of languages, a membership problem of which can be solved by the logarithmic number of random bits and the constant number of proof bits. (sounds miracle? The constant number of bits is actually needed instead of polynomial to proof a membership of the word.)
The original proof based on algebraic technique is quite complicated (around 20 pages of proof). The new proof based on combinatorial techniques (zig-zag products) was discovered this year by Irit Dinur.
Using other version of interactive proof systems we can capture PSPACE and NEXPTIME class and investigate some interesting properties of them.

NPO means NP optimization problem. NPO is a search version of NP class which is defined to be a class of decission problems. The NPO problem required to find a minimal (or maximal) solution among given one. For example, a Traveling Salesman Problem expressed as a search problem (Find a minimal lengh route in the graph which visit all vertices ones) would be an example of NPO problem. Usually NPO problem, a search version of NP decission problems belongs to FP^NP or FP^NP(log n) - hard classes indeed.
Since assuming P is not equal NP, there does not exist a polynomial algorithm to solve EXACTLY NP-hard-problems, given a NP-hard NPO problem it would be natural to ask, if a polynomial-time algorithm exists which can solve a problem with some approximation quality.
It was discovered that there exists a few approximation classes of NPO problems, which put certain bounds on approximation quality of algorithms for those problems. PCP theorem is useful to prove in-approximation properties of NPO problems.

Besides PCP theorem other important for theoretical computer science techniques will be introduced. Expanders are graphs which posses good expansion properties. (n,d,c) expander is a d-regular undirected graph with n vertices, such that if a set of vertices S chooses such that |S| < |n|/2, then a cardinality of a set of vertices adjacent to S is not less then c|S| Expanders are useful in computational complexity, error-correcting codes, communication networks.
Using expanders and PCP theorem we will prove n^\epsilon-inapproximability of MAX CLIQUE problem and NP-hardness of MAX 3SAT5 (SAT with 3 variables per clause and each variable is used not more then 5 times)

Pablo Barcelo's talk on Temporal Logic Over Unranked Trees

2005-07-20T09:09:00.000-07:00

Pablo Barcelo gives a talk at 16:00, Thursday 21, 2005
Topic: Temporal logic over unranked trees.
Abstract: We consider unranked trees, that have become an active subject of study recently due to XML applications, and characterize commonly used fragments of first- order (FO) and monadic second-order logic (MSO) for them via various temporal logics. We look at both unordered trees and ordered trees (in which children of the same node are ordered by the next-sibling relation), and characterize Boolean and unary FO and MSO queries. For MSO Boolean queries, we use extensions of the \mu - calculus: with counting for unordered trees, and with the past for ordered. For Boolean FO queries, we use similar extensions of CTL*. We then use composition techniques to transfer results to unary queries. For the ordered case, we need the same logics as for Boolean queries, but for the unordered case, we need to add both past and counting to the -calculus and CTL*. We also consider MSO sibling-invariant queries, that can use the sibling ordering but do not depend on the particular one used, and capture them by a variant of the \mu-calculus with modulo quantifiers.

Post's Lattice with Applications

2005-07-05T09:25:00.000-07:00

KRDB Internal Seminars

According to your requests after the last seminar on Monday, June 3d, I decided to make next seminar totally devoted to applications of "post lattice theory" (dichotomy results for SAT and circuit problems, tractable case of conjunctive query containment, expressive power of constraints).

Time: Wednesday, July 20th, 2005, 14:00
Speaker: Andrei Lopatenko
Topic: Post Lattice and Complexity Theory
Abstract: Exposition of application of a theory of boolean functions to complexity theory. The emphasize is on obtaining dichotomy results.
The following theorems and their proofs will be presented in full details :
1) [RW00] The complexity of CIRCUIT-SAT(B) problem (the problem is NP-hard if S_1 \subseteq [b], in all other cases it is PTIME solvable)
1a) Corollary of 1) LEwis theorem: SAT(B) is NP-hard if S_1 \subseteq B; in all other cases it is in PTIME

2) [RW00] CVP(B) is in NC if B \subseteq V \cup L \cup E; in all other cases it is PTIME-hard

3) [KV00] Schaefer Theorem (exposition will be given through algebraic approach proposed in KV00): CSP(B) is in PTIME, if B is a Schaefer structure; in all other cases CSP(B) is NP-hard

3) Corollary of 3). [Kv00] Testing whether a two-atom conjunctive query is contained in a conjunctive query can be done in PTIME

4)[JCS99] Other characterizations of tractable fragments of SAT

CIRCUIT-SAT is Circuit Satisfiability
CVP is Circuit Value Problem
CSP is Constraint Satisfaction PRoblem

RW00 Reigt Wagner, The complexity of problems defined by Boolean circuits, TR,
http://haegar.informatik.uni-wuerzburg.de/personen/ehemalig/streit/TRs/re-wa00.html
KV00 P. Kolaitis, M. Vardi, Conjunctive query containment and constraint satisfaction, JCSS 2000
http://www.cse.ucsc.edu/~kolaitis/papers/pods98f7.ps
JCG99 Jeavons Cohen Gyssens How to determine an expressive power of constraints, Constraints 1999
http://www.cs.rhul.ac.uk/research/constraints/publications/pubs-ps/how_to_determine.ps
BCRV42 Bohler, Creignou, Reith, Vollmer Playing with Boolean Blocks: Post's Lattice with Application to Complexity Theory, SIGACT NEWS Complexity Theory Column 42
BCRV43 Bohler, Creignou, Reith, Vollmer Playing with Boolean Blocks: Constraint Satisfaction Problems, SIGACT NEWS Complexity Theory Column 43

Seminar is postponed

2005-06-27T09:37:00.000-07:00

Joint seminar which was planned on June 29th is postponed.
Marijke Kett will give a talk on Thursday, June 30th, 11:30 am
Andrei Lopatenko will give a talk on Friday, July 1st, 2:00 am

Internal Joint Seminar June 29th 2005

2005-06-26T06:59:00.000-07:00

JOINT SEMINAR on June 29th

Part I. Factors affecting ontology development in ecology

Speaker: Marijke Keet
Location: Seminar room, 2nd floor, CS Faculty
time: 2:00 pm, Wed, June 29th, 2005
Type:
Abstract: Few ontologies in the ecological domain exist, but their development can take advantage of gained experience in other domains and from existing modeling practices in ecology. Taxonomies do not suffice because more expressive modeling techniques are already available in ecology, and the perspective of flow with its centrality of events and processes cannot be represented adequately in a taxonomy. Therefore, formal ontologies are required for sufficient expressivity and to be of benefit to ecologists, which also enables future reuse. We have created a formal mapping between the software-supported ecological modeling method and software tool STELLA and ontology elements, which simplifies bottom-up ontology development considerably and has excellent potential for semi-automated ontology development. However, the conducted experiments also revealed that ontology development for ecology is close to being part of ecological research that through the formalized representation of the knowledge more clearly points to lacunas and suggestions for further research in ecology.

for those of you who would like to skim or plough through the 16 pages, the article is online at http://www.meteck.org/DILS05_EcoFactors.pdf

Part II. Topics in Boolean Algebras: Seminar I. Post's Lattice

Speaker: Andrei Lopatenko
Location: Seminar room, 2nd floor, CS Faculty
time: 3:00 pm, Wed, June 29th, 2005
Type: Foundations
Part II (cont Part I)
Closure properties of boolean relation. Co-clones.
Co-clones of boolean relations. Invariants of booleans functions and polymorhisms of boolean relations. Geiger-Bodnarchuk theorem.
Tractable subcases of boolean Constraint Satisfaction Problem. Closure Properties of Constraints.Complexity of co-Clones (Creignou 1978)
Clones and co-Clones for finite (k-ean) function and relations. Uncountable number of 3-ean clones. A finitely generated 3-ean clone whose identitities are not finitely based (Murskii)
Schaefer's dichotomy (Schaefer-1978). Uniform results for Schaefer dichotomy (Kolaitis-Vardi). Recognition of relations \in Schaefer class. Tractability results for restricted cases of query containment. Part III (30 minutes brief survey of results, proofs are not presented)A dichotomy for Max-SAT (Creignou 1995) and Min SAT (Kirousis Kolaitis 2001). Counting, Bounded Alternation. A complete classification for constraint satisfaction problem under AC_0 isomorphisms, 6 AC_0 isomorphism types (Allender et al 2004), a dichotomy for 3-element domains (Bulatov 2002). expressive power of constraints (Jeavons et al 1999

Internal Seminar May 18th 2005

2005-05-15T07:27:00.000-07:00

Topics in Boolean Algebras: Seminar I. Post's Lattice

Speaker: Andrei Lopatenko
Location: Seminar room, 2nd floor, CS Faculty
time: 11:00 pm, Wed, May 18th, 2005
Type: Foundations
Abstract: Seminar may be splitted into two parts which may be hold on different days. Part I
Background: Closure systems and closure maps, clones in Universal Algebra. Polarities and Galois connections.
Clones of boolean functions. Post's lattice.The Finite-Basis Theorem (Pippenger's version of Marchenkov's proof is presented.)
The complexity of some problems in Post's lattice. PTIME/NP-complete for Circuit-SAT and SAT and NC/P-complete for Circuit Value Problem (Reith Wagner, 2000). The complexity of clones (Bohler-2001)

Internal Seminar. March 09th, 2005

2005-03-09T10:12:00.000-08:00

The Consistent Query Answering for databases with linear and aggregate constraints over numerical domains.

Computation Complexity and Approximability of Database Fix and the (Aggregate) Consistent Query Answer problems
Speaker: Andrei Lopatenko
Location: Seminar room, 2nd floor, CS Faculty
time: 15:00 pm, Wed, March 09th, 2005
Type: Foundations
Abstract: Consistent query answering is the problem of computing those answers from a database that are consistent with respect to certain integrity constraints that the database as whole may fail to satisfy. Those answers are characterized as invariant under minimal forms of restoring the consistency of the database. In this context, we study the problem of repairing databases by fixing numerical data at the attribute level. For their relevance in database applications with numerical domains, we consider denial and aggregate constraints. After providing a quantitative definition of database fix, we investigate the computational complexity of different problems, such as the existence and verification of fixes, and deciding consistency of answers to conjunctive aggregate queries. We show tractability for special cases; and provide approximation algorithms for some of the hard cases.

Internal Seminar. September 24th 2004

2004-09-24T10:14:00.000-07:00

Cycles in P2P & DB networks

Speaker: Andrei Lopatenko
Location: Seminar room, 2nd floor, CS Faculty
time: 15:00 pm, Wed, 21th September, 2004
Title: Cycles in P2P Networks
Type: Applications
Abstract:
1 (Review)Cycles in search P2P networks
1.1 Routing indices by Garcia-Molina
1.2 How cycles change quality of query answer in routing indices search networks
2 (Review) Tabled Logical programming, tabled resolutiong (SLG)
2.1 tabled resolution to
2.2 distributed prolog
3 Cycles in P2P and Database system
3.1 Cycles in Piazza (Alon Halevy\Washington Univer. P2 DM system)
3.2 Decomposition of the graph into independent paths (cycles) ()
3.3 Distributed algorithm for 3.2

Seminar. December 3d, 2003

2003-12-03T10:18:00.000-08:00

Peer-to-Peer Database Systems

Speaker: Prof. Enrico Franconi
Location: Seminar room, 2nd floor, CS Faculty
time: 12:30 pm, Wed, 3 December, 2003
Title: Peer-to-Peer Database Systems
Type: Current Research
Abstract
In this talk I'll give a logical and computational characterisation of robust peer-to-peer database systems. I first define a precise model-theoretic semantics of a p2p system, which allows for local inconsistency handling. I then characterise the general computational properties for the problem of answering queries to such a p2p system. Finally, I'll devise tight complexity bounds and distributed procedures for the problem of answering queries in few relevant special cases. This is joint work with Andrei, Gabi Kuper, and Luciano Serafini.

Seminar November 19th 2003

2003-11-19T10:17:00.000-08:00

Reasoning over Temporal Conceptual Schemas

Speaker: Dr. Alessandro Artale
Location: Seminar room, 2nd floor, CS Faculty
time: 12:30 pm, Wed, 19th November, 2003
Title:Reasoning over Temporal Conceptual Schemas
Type: Current Research
Abstract
The seminar presents a logical formalism for capturing temporal conceptual models used in the design phase of temporal databases. The proposed logic is a natural combination of the description logic DLR and the point-based linear temporal logic with Since and Until. The expressive power of the resulting logic, DLR_US, is illustrated by providing a systematic formalisation of the most important temporal entity-relationship models appeared in the literature. I also present a query language where queries are non-recursive Datalog programs and atoms are complex DLR_US expressions. Complexity results for the problem of checking query containment under the constraints defined by DLR_US conceptual schemas, as well as the reasoning problems of schema satisfiability and logical implication are presented.

Seminar. November 5th 2003

2003-11-05T10:15:00.000-08:00

Undecidability

Speaker: Andrei Lopatenko
Location: Seminar room, 2nd floor, CS Faculty
time: 12:30 pm, Wed, 5th November, 2003
Title: Undecidability
Type: Foundations
Abstract
The aim of the seminar is to review some basic results in Theory of Recursive Functions, especially in their connection to Mathematical Logic, and Database Theory. The seminar is intended to refresh knowledge in foundations and review some practical methods to prove undecidability in areas of KRDB. The emphasize is done in practical methods, but not in philosophical background. Due to limitations of time and knowledge of the speaker some proofs are not given in details or ommited.
Content
1 What is undecidability
1.1 main definitions
1.2 undecidability and definability of theories
1.3 undecidability and finite axiomatizability/categoricity of theories
1.4 degrees of undecidability
2 Some 'classical' undecidable problems
2.1 Halting problem
2.2 Hilbert's 10th problem and dioffant equations
2.3 Thue congruences
2.4 Groups and semi-groups (Post, Markov)
2.5 Post Correspondence Problem and other combinatorial undecidable problems
2.6 Finite Satisfiability (Trahtenbroth's theorem)
3 Applications - Undecidability in Databases
3.1 Query answering over FOL views, query answering over datalog views
3.2 Undecidability of implication for fd's + ind's
3.3 Query Containment of Datalog Queries
3.4 Query answering in Global As View approach under constraints in global schema (ind's + keys)
Literature
1. J. Shoenfield, Mathematical Logic, Addison-Wesley 1967
2 H. Roges, Theory of Recusrive Functions and Effective Computability, McGraw-Hill, 1967
3. M. Davis, Undecidable Problems, in Barwise, Handbook of Mathematical Logic
4. Enderton, Theory of Recursion, in Barwise, Handbook of Mathematical Logic
5. H.-D. Ebbinghaus, J. Flum, Finite Model Theory, Perspectives in Mathematical Logic, Springer, 1995
6 Abitebull, Hull, Vianu, Foundations of Databases, Addison-Wesley, 1995
5. Y. Manin A Course in Mathematical Logic, Graduate Text in Mathematics, Springer-Verlag, 1977