17th Estonian Winter School in Computer Science (EWSCS)
XVII Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 26 -March 2, 2012

Student Talks 2012 (abstracts)

A New Upper bound for (n,3)-MAXSAT

Ivan Bliznets
St. Petersburg University of the Russian Academy of Sciences, Russia

It is still not known whether the satisfiability problem (SAT), and hence maximum satisfiability problem (MAX-SAT), can be solved in time $poly(|F|) c^n$, for $c<2$, where $c$ is a constant, $n$ is the number of variables, and $F$ is an input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximal number of variable occurrences or the length of the formula is bounded. In my talk, we consider the $(n,3)$-MAX-SAT problem --- a special case of MAX-SAT where each variable appears in a formula at most three times. We present a simple algorithm with running time $O^*(2^{n/3})$. As a byproduct we also obtain a polynomially solvable subclass that may be of independent interest.

Condition-Specific Gene Clustering

Briti Deb
University of Tartu, Inst. of Computer Science, Estonia

Since the findings by Francis Crick of what he called the Central Dogma about the flow of information in living cells, traditional biological research has taken primarily a reductionist approach, (i.e. molecular approach) focusing on single genes or proteins. The growing need for a global (or holistic) approach to biological research can be found in the work of [1] where the author illustrates a fact that several genes contribute to a disease, and molecules interact with more than one partner, needing a holistic approach. This research is aimed at investigating biology taking a global (or holistic) approach (i.e. cellular approach), aiming to cluster genes based on conditions they express, which in future we believe might help in building gene networks. It has been shown by [2] that the discovery of novel biological knowledge relies much upon the use of data mining techniques such as clustering. In this paper, we aim to investigate data mining algorithms on microarray data to cluster genes based on conditions, and present a comparison study of several algorithms, a necessary research which is also corroborated by [1]. This research also starts to investigate on how the gene clusters can be used to predict gene networks [3], a problem which largely remains an unsolved problem [4]. (Joint work with Dr. Satish Srirama.)

[1] P. D’haeseleer, S.Liang and R. Somogyi, Gene Expression Data Analysis and Modeling, Session on Gene Expression and Genetic Networks, Pacific Symposium on Biocomputing, 1999, Hawaii , January 4-9, 1999.
[2] J Handl, et al, Computational cluster validation in post-genomic data analysis, Bioinformatics, 2005 - Oxford Univ Press
[3] P. D'haeseleer, Reconstructing Gene Networks from Large Scale Gene Expression Data, PhD Thessis, cs.unm.edu, 2000.
[4] D. Marbacha, et al, Revealing strengths and weaknesses of methods for gene network inference, pnas, 107, 6286-6291, 2010.

Certified parsing

Denis Firsov
Institute of Cybernetics at TUT, Estonia

Parsing is a fundamental component of many software pieces. The ultimate goal of our project is to implement a parser generator for context-free languages, which, given a context-free grammar, should be able to provide a parser together with an independently checkable certificate of its correctness.

As a first approximation of our main goal, we implemented a parser generator for regular languages and showed its correctness using the Agda programming language. Specifically, we programmed a transformation of regular expressions into a Boolean-matrix based representation of finite automata. And we proved (in Agda) that a string matches a regular expression if and only if the finite automaton accepts it.

Diophantine hierarchy

Alexander Knop
St. Petersburg State University, Fac. of Math. and Mechanics, Russia

Adelman and Manders (1975) defined the class D of `non-deterministic diophantine' languages. A language L is in D iff there are polynomials p and q such that $x in L Leftrightarrow exists y_1, dots, y_ n < 2^{q(|x|)}~p(x , y_1 , dots, y_n ) = 0$ (in this formula, bit strings are treated as natural numbers). While clearly D is a subset of NP, it is unknown whether these classes are equal.

The well-known polynomial hierarchy PH consists of complexity classes constructed on the basis of the class NP. We consider a hierarchy constructed on the basis of D in a similar way. We prove that D is in the second level of the polynomial hierarchy, and hence all the classes of the two hierarchies are successively contained in each other.

Permutation Fewnomials and Their Applications is Cryptography

Mikhail Rybalkin
St. Petersburg Department of Steklov Institute of Mathematics, Russia

This work is devoted to studying the properties of permutation polynomials over finite fields, i.e. polynomials that induce one-to-one mapping. Such polynomials can be treated as an alternative representation of permutations. Dependency between permutation polynomials and properties of the induced permutations are nontrivial, and even for binomials and trinomials it is an open problem to describe all such permutation polynomials, and to find an efficient algorithm of finding inverses of such polynomials. Permutation polynomials can be used in cryptography as a cipher functions. The RSA cryptographic algorithm uses permutation monomials as an encryption function, and it is an open question whether it can be generalized by using general permutation polynomials. We present some numeric experiments with permutation polynomials that lead to hypotheses about their properties. Based on those we give a proof that a generalization of RSA using permutation binomials is not secure.

Lower bounds for myopic DPLL algorithms with a cut heuristic

Dmitry Sokolov
St. Petersburg Department of Steklov Institute of Mathematics , Russia

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are also known for some classes of DPLL algorithms; this lower bounds are usually based on reductions to unsatisfiable instances. In this paper we consider DPLL algorithms with a cut heuristic that may decide that some branch of the splitting tree will not be investigated. DPLL algorithms with a cut heuristic always return correct answer on unsatisfiable formulas while they may err on satisfiable instances. We prove the theorem about effectiveness vs. correctness trade-off for deterministic myopic DPLL algorithms with cut heuristic. Myopic algorithms can see formulas with erased signs of negations; they may also request a small number of clauses to read them precisely.

We construct a family of unsatisfiable formulas $Phi^{(n)}$ and a polynomial time samplable ensemble of distributions $Q_n$ concentrated on satisfiable formulas such that every deterministic myopic algorithm that gives a correct answer with probability $1-o(1)$ on a random formula from the ensemble $Q_n$ runs exponential time on the formulas $Phi^{(n)}$.

The material of the talk was presented at the 22nd International Symposium on Algorithms and Computation (ISAAC 2011) and published in Springer LNCS. (Joint work with Dmitry Itsykson.)

Boolean circuit complexity of finite automata

Maris Valdats
University of Latvia, Dept. of Computer Science, Latvia

State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. We consider a new measure of descriptional complexity of finite automata -- BC-complexity.

The state space S of an automaton is replaced by a state register (with logS state bits) and the transition function is expressed as a boolean function. For automata with a big number of states but simple structure of transition function this seem to be a more natural representation.

These complexity measures can be compared - it turns out that the BC-complexity of automata with fixed number of states can vary exponentially. For most of automata these complexity measures gives approximately the same value, but in some cases the BC-complexity can be much smaller.

But the most interesting thing is connected with minimization: it turns out that minimization of the number of states sometimes can lead to a superpolynomial increase of BC-complexity. It is sometimes worth to keep equivalent states, that can make transition function much simpler.

This talk was presented at DCFS 2011 workshop and published in Springer LNCS.

Valid CSS! Valid XHTML 1.0 Strict Last changed November 26, 2014 19:55 EET by local organizers, ewscs12(at)cs.ioc.ee
EWSCS'12 page: http://cs.ioc.ee/ewscs/2012/