Dear colleagues,

a Franco-Russian workshop (Algorithms, Complexity and Application 2013, 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 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.


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)