Yury Lifshits  About me  Publications  Talks  Teaching  Þðèé Ëèôøèö 
Algorithms for data mining:
 Disorder inequality: A combinatorial approach to nearest neighbor search,
with Navin Goyal and Hinrich Schütze, submitted, 2007. 
Maximal Intersection Queries in Randomized Graph Models,
with Benjamin Hoffmann and Dirk Nowotka. Accepted to CSR 2007.  Estimation of the Click Volume by Large Scale Regression Analysis,
with Dirk Nowotka. Accepted to CSR 2007. // The Best Paper in Applications/Technology Track

Speeding up HMM decoding and training by exploiting sequence repetitions,
with Shay Mozes, Oren Weimann, and Michal ZivUkelson, submitted, 2007. 
Tiling Periodicity, look also at talk slides.
with Juhani Karhumäki and Wojciech Rytter. CPM 2007.  Processing Compressed Texts: A Tractability Border,
look also at talk slides.
CPM 2007.
Draft version was called "Solving Classical String Problems on Compressed Texts".  Quering and Embedding Compressed Texts,
look also at talk slides.
with Markus Lohrey, MFCS'06, LNCS 4162, pp. 681692, SpringerVerlag, 2006.  Window Subsequence Problems for Compressed Texts,
look also at talk slides.
with Patrick Cegielski, Irene Guessarian and Yuri Matiyasevich. CSR'06, LNCS 3967, pp 127136, SpringerVerlag, 2006. 
On the Computational Complexity of Embedding of
Compressed Texts, also look at Russian version
Diploma thesis, June 2005.  Algorithms and Complexity Analysis for Processing Compressed Texts (In Russian), see also summary called "Avtoreferat". PhD thesis, Spring 2007.

Decidability of Parameterized Probabilistic Information
Flow,
with Daniele Beauquier and Marie Duflot. CSR 2007. 
Guaranteed slowdown, generalized encryption
schemes and function sharing,
Proc. of Institute of System Programming of Russian Academy of Science, 2006.  Program Obfuscation: a Survey (In Russian), unpublished.

Fast Exponential Deterministic Algorithm
for Mean Payoff Games,
with Dmitri Pavlov. Zapiski Nauchnyh Seminarov POMI, Vol. 340, pp. 6175, 2006.  Partitioning
a kconnected graph,
"Discrete Mathematics and Applications", Volume 15, No. 4, pp. 365377, VSP, 2005.  A lower
bound on the size of epsilonfree NFA corresponding to a regular
expression
Information Processing Letters, vol 85/6, pp 293299, Elsevier, 2003.

Development Principles for Computing Theory (In Russian)
My obligatory essay on history of science  Education 2.0 (In Russian).