Lecture on Tilings given by Prof. Richard Stanley

I have found slides of a public lecture on tilings given by Richard Stanley on July 16, 2004.
Richard Stanley who is currently the Norman Levinson Professor of Applied Mathematics at M.I.T. was named Clay Senior Scholar at the Park City Mathematics Institute (IAS/PCMI) program on Geometric Combinatorics (July 2004).
Perhaps, almost everybody interested in combinatorics read his "Enumerative Combinatorics" vo. 1 and 2 (at least, come chapters of it).
Now he works on a book "Hyperplane arrangements". See, a draft "An Introduction to Hyperplane Arrangements"(46 pages) or Stanley's lecture notes on Hyperplane Arrangements (22 pages)

Our article is accepted to DBPL-2005

Today I have got a notification that our article was accepted to DBPL-2005.
DBPL is one of the top level symposiums in database theory.
The article is
Leopoldo Bertossi, Loreto Bravo, Enrico Franconi and Andrei Lopatenko, "Complexity and Approximation of Fixing Numerical Attributes in Databases Under Integrity Constraints"
The CORR(arXiv) version is here cs.DB/0503032.
Acceptance rate is around 26% (17 out of 63). Taking into account DBPL PC and quality of submissions(I have reviewed some of them) + impact factor of DBPL, quality of papers published in previous years, I am quite proud by this result.
At this point I see directions to extend our research pretty well.

Post Lattice and Complexity Theory

UNIBZ KRDB Internal Seminars
According to requests of people, attended KRDB seminar on Monday, June 3d, I decided to make next KRDB 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

Today I gave a talk (seminar) on boolean co-clones, Galois connections between clones and co-clones, extension of theory of boolean functions on k-ean domain.
I'll put slides online in a few days.
Most people attending seminar were interested in application of theory boolean clones to prove dichotomy results (like Reith-Wegener theorem, Schaefer Dichotomy, Dalmau, Bulatov results). I think I'll prepare two hour tutorial on dichotomy results only.

UPDATE

I have updated my home page
Links to google map images of my hometown and Bolzano are added