Student Talks 2015 (abstracts)
Heuristic time hierarchies via hierarchies for sampling distributions
St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Federation
We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get that P is not included in BPTime[nk], if one way functions exist. As far as we know this result was not known before.
We also show that our technique may be extended for time hierarchies in some other heuristic classes.
Joint work with Dmitry Itsykson and Dmitry Sokolov.
Paths between cross polytopes: searching for optimal fixed-point polynomials
Due to the nature of the protocols we have previously used for evaluating some elementary functions secretly, we need to evaluate some functions using fixed-point evaluation polynomials on a small range [a,b]. For these methods, polynomials with a minimal error are needed, however, using fixed-point multiplication adds additional errors that are difficult to estimate and minimize analytically.
We have taken a different approach and performed searches using the convexity of solutions in the space of polynomials of rank n. We have noticed that when we take the convex cover of small cross polytopes around two local optimal solutions, then that convex cover contains a path of points with fixed-point coordinates from one solution to another. We have used this property to perform search in the space of polynomials of rank n. This is still an ongoing work.
FOTIS: building an automatic face recognition system for The National Archives of Estonia
University of Tartu, Inst. of Computer Science, Estonia
The National Archives of Estonia have over 500 000 digitized photos in their database. A solution for organizing and categorizing such a large database better is highly desired. The goal of the FOTIS project is to develop an automatic face recognition system to tag persons appearing in the photos. In particular, we have used the standard OpenCV library to extract faces from photos and then a convolutional neural network to classify them as belonging to one or the other person. With a restricted dataset of 1000 faces of the 23 most occurring persons we achieved an accuracy of 76%. Unfortunately this result does not generalize well enough for practical uses yet – faces of unknown persons were classified as one of the 23 persons with a probability higher than 99%. For example anybody who wears glasses is Mart Laar or anybody who has a mustache is Siim Kallas. We identified the main problem to consist in too few manually labeled photos and too coarse labels, which resulted in a too small dataset with too few classes. To overcome these problems we discuss possible improvements to our approach including transfer learning, generative pre-training and clustering using stacked autoencoders. We welcome anyone interested to join us in our efforts to make this project a valuable tool for the National Archives of Estonia and other organizations.
About the function Q(n)
University of Latvia, Dept. of Physics and Mathematics, Latvia
This work studies the problem of finding the number of binary strings with the same length that are as „close” as possible to each other. This problem appears in investigating Boolean functions. We show that this problem is related to a specific k-dimensional hypercube graph coloring problem, isoperimetric inequalities for graphs, Harper’s theorem about Hamming balls in hypercube graphs and to a function defined in this work and denoted Q(n). Our main result consists in establishing optimal upper and lower bounds of this function (up to constants). We also show that this function „oscillates” between the bounds obtained infinitely many times.
Precomputed Verification of Multiparty Protocols with Honest Majority
We present a generic method for turning passively secure protocols into protocols secure against covert attacks. We use beaver triples to make it possible to verify a protocol execution by running it locally on shares. The method adds a longer preprocessing phase and a short post-execution verification phase to the protocol, allowing a misbehaving party to escape detection only with a negligible probability. The execution phase, after which the computed protocol result is already available for parties, has only a negligible overhead added by our method. We present our result for three parties, but it should be possible to extend it to any number of parties. The verification can be easily adjusted to computation on rings, not only on fields, and hence it is easily applicable to existing secure multiparty computation platforms.
Joint work with Peeter Laud.
An Algebraic Geometric Approach to Lattice Configurations of Low Complexity
University of Turku, Finland
The motivation for this work are two open combinatorial problems. Nivat's conjecture (1997) states that, if there is a coloring of the infinite two-dimensional lattice Z2 by finitely many colors that contains at most M*N distinct rectangular patterns of size MxN for some integers M and N, then the coloring must be periodic. The second problem concerning periodic tilings by Lagarias and Wang (1996) will be introduced in the talk.
We developed a new method using techniques from algebraic geometry and linear algebra to approach these problems. They both consider a two-dimensional configuration, which we represent as formal power series in two variables. Then we consider its annihilators -- polynomials, after multiplication by which the formal power series vanishes.
We can prove that a multidimensional configuration that has a non-zero annihilator can be written as a sum of periodic integer configurations, having possibly unbounded coefficients. Applying that to Nivat's conjecture we get the following partial result: if there are infinitely many pairs of integers M, N such that a two-dimensional configuration has at most M*N distinct rectangular patterns of size MxN, then it is periodic.
Joint work with Jarkko Kari.
November 26, 2014 19:55 Europe/Helsinki (GMT +02:00)
local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/