Dear colleagues,
a Franco-Russian workshop (Algorithms, Complexity and Application 2013,
aca2013.mccme.ru) will happen 21-23 June in Moscow (Poncelet laboratory, at
the MCCME building, Bolshoi Vlaievsky, 11). It is planned as an informal
meeting where people will speak about their current work, with no published
proceedings. We invite all interested people to come, no registration is
needed. (If you have some questions or need some help about the venue and
other practical matters, feel free to write to aca2013@mccme.ru.) The
preliminary program is listed below; talks are planned from 10:00 to 18:00
with a lunch break, 25--35 minutes each; blackboard, chalk (and even a
projector if you really need it) will be available. There are few free
slots remaining, so talk suggestions are still invited.
PRELIMINARY PROGRAM
21, Friday
Registration (9:30--10:00)
Fernique: Flipping the Socolar-Taylor aperiodic tile
Belov, Ivanov-Pogodaev: Local rules for aperiodic hierarchical tilings and
finitely presented nil-semigroups
[The talk is devoted to the topological approach for hierarchical tilings.
For any hierarchical locally finite graph we can construct the set of
forbidden sequences of edges (words) such that any graph without these
forbidden words is isomorphic to the initial hierarchical graph. // These
facts correspond to Goodmann-Strauss theorem about aperiodic hierarchical
tilings. // Also, this can be used as construction method for algebraic
objects.// We use this method to costruct an finitely presented infinite
nil-semigroup, answering on the Shevrin problem. // The method is based on
considering the paths on some tiling as non trivial elements of a
semigroup. Also, the structure of tiling induces the relations in the
semigroup. // The tiling can be presented by the finite number of rules, so
the semigroup would have the finite number of defining relations. // There
are no periodic paths on the tiling so there are no periodic words in the
semigroup. // The subject is related to other Burnside type problems in
groups and rings.]
Bedaride: An example of substitutive tiling of the plane: Link with the
Rauzy fractal.
(with A. Hilion and T. Jolivet)
Mitrofanov: TBA
Helloiun: Characterization of limit measures of iterated cellular automata
Knop: Diophantine hierarchy
Theyssier: Lattice dimension, dynamics and complexity in symbolic space
22, Saturday
Scedrov: Collaborative Systems (survey)
[We discuss a model of collaboration, introduced in a joint work with
Kanovich and Rowe, in which the participants are unwilling to share all
their information with each other, but some information sharing is
unavoidable when achieving a common goal. The need to share information and
the desire to keep it confidential are two competing notions which affect
the outcome of a collaboration. Our model is based on the notion of a plan
which originates in the AI literature. We also consider an extension of the
model which allows for updates of values with fresh ones, such as updating
a password. // All the players inside our system, including potential
adversaries, have similar capabilities. They have bounded storage capacity,
that is, they can only remember a bounded number of facts. This is
technically imposed by allowing only the so-called balanced actions, that
is, actions that have the same number of facts in their pre and post
conditions. We investigate the complexity of the planning problem, whether
the players can reach a goalwhile avoiding certain critical configurations
along the way. We show that this problem is PSPACE-complete. The complexity
is lowered to NP-completeness for the class of so-called progressing
collaborative systems, intended to describe administrative processes, which
normally have a progressing nature: once an item in an activity to-do list
is checked, that activity is not repeated. // As an application we turn to
network security protocol analysis and demonstrate that when an adversary
has enough storage capacity, then many known protocol anomalies can also
occur in the presence of a bounded memory intruder. We believe that
precisely this is a theoretical reason for the
successful use in the past years of model checkers in security protocol
verification. In particular, the known anomalies arise for bounded
memory protocols, where there is only a bounded number of concurrent
sessions and the honest participants of the protocol cannot generate an
unbounded number of facts nor an unbounded number of fresh values. This led
us to the question of whether it is possible to infer an upper-bound on the
memory required by the adversary to carry out an anomaly from the memory
restrictions of the bounded protocol. We answer this question negatively.
This is joint work with Max Kanovich, Tajana Ban Kirigin, and Vivek Nigam.]
Oparin: Query complexity and local search problems
Sokolov: Lower bounds on DPLL algorithms with splitting over linear
functions
on unsatisfiable formulas
Itsykson: On short heuristic proofs
Makhlin -- Vereshchagin: Short lists of short programs
Vyugin: Algorithimic aspects of probability laws
Andreev -- Kumok: $\alpha$-null sets: strong vs. weak
23, Sunday
Makarychev: Tutorial, TBA
Kucherov: Seed-based sequence search: some theory and some applications
Babenko -- Kolesnichenko -- Starikovskaya TBA
Ostroumova -- Raygorodsky: Around web-graphs (? TBA)
Shabanov: Extremal combinatorics (? TBA)
Dektyarev: Circuit and garden-hose complexity (? TBA)