[ Homepage ] [ Koduleht ] [ Mājaslapa ]
Slides of the talk: [ ppt ] [ pdf ]
Abstract:
It has long been known that any Boolean function that depends on n
input variables has both degree and exact quantum query complexity of
Θ(log n), and that this bound is achieved for some functions. In this
paper we study the case of approximate degree and bounded-error quantum
query complexity. We show that for these measures the correct lower
bound is Θ(log n / log log n), and we exhibit quantum algorithms for
two functions where this bound is achieved.
Full text paper : http://arxiv.org/abs/1206.0717
Slides of the talk: [ pdf ]
Abstract: Query complexity is one of the most popular complexity measures of quantum algorithms, mostly because of the existence of powerful tools for proving upper and lower bounds. One of these tools is the adversary bound. Stated as a semi-definite program, it serves as both upper and lower bound for quantum query complexity. In this talk we describe a recent framework of learning graphs for proving upper bounds using the adversary method, and survey its applications.
Abstract: We present a new non-periodic random number generator based on the shrinking generator. The A-sequence is still generated using a LFSR, but the S-sequence is replaced by a finitely generated bi-ideal - a non-periodic sequence. The resulting pseudo-random sequence performs well in statistical tests. We show a method for the construction of an infinite number of finitely generated bi-ideals from a given A-sequence, such that the resulting sequence of the shrinking generator is nonperiodic. Further we prove the existence of what we call universal finitely generated bi-ideals that produce non-periodic words when used as the S-sequence of a shrinking generator for all non-trivial periodic A-sequences.
Abstract: The dynamics of a physical system is linked to its geometry by Noether's theorem, which holds under standard hypotheses such as continuity. We explore the existence of similar links for discrete systems. As a testbed, we take the Ising spin model with both ferromagnetic and antiferromagnetic bonds. We show that, for this family of systems, energy not only acts as a generator of the dynamics, but also is conserved precisely when the dynamics is time-invariant as in Noether's theorem.
Slides of the talk: [ pdf ]
Abstract: Considering a stochastic
automaton as an analogue of
a physical system, one can imitate in the field of such automata
several constructions known well in the quantum logic approach to
describing physical systems. To simplify the needed mathematical
apparatus, we deal with non-deterministic (ND) rather than stohastic
automata; then these constructions become purely algebraic.
With an ND-automaton A,
a certain orthocomplemented poset L (a
generalization of a Boolean algebra), called the logic of A, is
associated in a canonic way. Every filter of the logic L is then
interpreted as a generalized state of A, while a function
whose domain
is a maximal orthogonal subset of L
is interpreted as an "observable"
of A. In
particular, every input word of A
gives raise to such an
observable. Therefore, an ND-automaton can be presented as a triple
(L,O,S), where L is its logic, O is a sufficiently
large set
observables, and S,
a sufficiently large set of states (i.e., filters).
In the talk, we discuss such algebraic presentations of ND-automata.
Abstract: We describe our ongoing work on certified parsing of context-free languages. We have implemented the functional core of the Cocke-YoungerKasami (CYK) parsing algorithm (based on multiplication of matrices over the powerset of the non-terminals of a normal-form grammar) and proved its correctness in the Agda dependently typed programming language.
Abstract: We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.
Abstract: Quantum Markov chains have certain role in the field of quantum computation. It is known from classical Markov chains theory that after application of a chain sufficiently many times, one obtains a stationary distribution. The talk will discuss the dynamics of this process in the case of a quantum operation.
Slides of the talk: [ pdf ]
Abstract: Functional reactive programming (FRP) is a declarative programming paradigm that uses time-varying values and events for describing temporal behavior. FRP programs are constructed using causal operations, so that they are able to produce output solely on the basis of already known input. In this talk, we describe a way to express causality of FRP operations using concepts of category theory. The key idea of this approach is to focus on the time dependent knowledge about values, not on the values themselves. We show that this makes it impossible to express liveness conditions in certain cases.
Slides of the talk: [ pdf ]
Abstract: For many classical NP-hard
problems in graph theory
and combinatorics, currently the asymptotically fastest known exact
algorithms rely on algebraic tools such as group and semigroup
algebras. This talk will review one such framework, the Mőbius algebras
of finite lattices (see e.g. [1]), together with selected applications
on the subset lattice.
[1] A. Bjorklund, T. Husfeldt, P. Kaski, M.
Koivisto, J.
Nederlof, and P. Parviainen,
Fast zeta transforms for lattices with few irreducibles,
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2012, Kyoto, 17?19 January, 2012), SIAM,
Philadelphia,
PA, 2012, pp. 1436-1444.
http://siam.omnibooksonline.com/2012SODA/data/papers/244.pdf
Slides of the talk: [ ppt ]
Abstract: We present results of analysis of some special classes of nonlocal games. These games are used as a model for displaying nonlocal properties of quantum mechanics. From this point of view the most interesting among them are symmetric games, since they demonstrate the biggest difference between classical and quantum worlds. On the other hand, this set of games can be analyzed in the most efficient way. We consider multiplayer XOR games with 1-bit inputs and 1-bit outputs which are symmetric w.r.t. permutations of players. Vast majority of non-local games from this class have positive difference beetween their classical and quantum values. In order to show this fact we performed both numerical and analytical investigations on the expected value of random symmetric game. We provide a tight bound for the expected value of classical game and "numerical evidence" that the value of quantum game is significantly bigger.
Abstract: Secret sharing can be used to perform privacy-preserving joint computation. The models used this far have been using finite fields GF(2n) which have good algebraic properties but which do not agree very naturally with the computer architecture - to do arithmetic, one often needs to use comparison operators that are expensive in this paradigm. We studied the possibility of using the rings Z2n instead. The algebraic properties of the rings Z2n are somewhat weaker and linear algebra is somewhat more complicated, however, it agrees very naturally with computer architecture. An object that we called a weakly invertible matrix appeared to be central in this research. The weakly invertible matrix is a rather natural generalization of invertibility - they are such matrices where no row vector can be expressed as a linear combination of other row vectors. We showed the connection between secret and partially functional secret-sharing schemes and weakly invertible matrices, studied the properties of weakly invertible matrices and achieved some results which may make the construction of secret and partially functional secret sharing schemes over rings Z2n easier.
Slides of the talk: [ pdf ]
Abstract: Closure properties of some classes of right innite words have been studied extensively, we are interested in the general algebraic structure of right infinite words. We investigate preorder of morphism invariant classes, and show that it is not a semi-lattice.
Slides of the talk: [ pdf ]
Abstract:
Identity-based cryptography does away with the need to distribute
public-key certificates because each party's name can also serve as
his/her public key. Identity-based analogues for various primitives
(encryption, signing, etc.) have been proposed; their usage may reduce
the deployment costs of cryptography in some scenarios.
A generic group is an idealized construct, representing a group where
nothing about the internal representation of the group elements is
known. Group operations and equality checks are the only possible
operations with the elements. Several group-theoretic hardness
assumptions are provably valid in the generic group. In cryptography,
generic group model can be used to provide upper bounds on security of
certain constructions, as well as to prove their security against
generic attacks.
In this talk we show that identity-based encryption (IBE) schemes
cannot be constructed in the generic group model. In other words, for
any purported IBE scheme there exists an adversary that breaks its
security. The adversary is not necessarily efficient, but it is
constrained to perform only a small number of group operations. The
result shows that the security of an IBE scheme cannot be based on any
hardness assumption that is valid in the generic group.
Slides of the talk: [ pptx ] [ pdf ]
Abstract: We propose two basic NIZK
arguments, one for
Hadamard product of two vectors, and another one for a shift of a
vector. The first argument is based on the corresponding argument of
Lipmaa (TCC 2012), but makes use of Fast Fourier Transform and
Pippenger's multi exponentiation algorithm to achieve quasilinear (as
opposed quadratic) computational complexity. The shift argument seems
to be novel.
Based on the new basic arguments, we propose a NIZK argument for subset
sum. This seems to be the only known (direct) sublinear NIZK argument
for some other NP-complete language than Circuit-SAT. Moreover, it is
significantly more efficient than the known sublinear Circuit-SAT
arguments by Groth (Asiacrypt 2010) and Lipmaa. In addition, we show
that the new arguments can be used to speed up the recent range
argument by Chaabouni, Lipmaa and Zhang (FC 2012).
Finally, we combine the subset sum argument and the range argument to
propose a direct sublinear NIZK argument for another NP-complete
language, decision knapsack.
Full text paper : http://eprint.iacr.org/2012/548
Abstract: Open Induction on Cantor space (OI) is a principle classically equivalent to Dependent Choice, which is, unlike the later, closed under double-negation translation and A-translation. In the context of Constructive Reverse Mathematics, Wim Veldman has shown that, in presence of Markov's Principle, OI is equivalent to Double-negation Shift (DNS). With Danko Ilik, we have reworked Veldman's proof to give a constructive proof of OI, where DNS is interpreted using delimited control operators.
Abstract: Program slicing is a program transformation technique to extract from a given program the lines that influence computation of some values of special interest. The program that is obtained by leaving out all unnecessary code is called a slice. The well-known formal definitions of what it means to be a slice are designed for deterministic setting. The talk will give an overview of the issues that arise in the case where programs include non-deterministic operations. Non-determinism is often masked by additional parameters in formal semantics but we argue that, for specification of program slicing, the usual type of additional parameter (e.g., a generator that produces a stream of random values) is not appropriate. We propose using generators that are themselves parametrized on run-time instances of program points. In our ongoing work, we develop a framework for handling run-time instances of program points in programs and their slices uniformly and prove the correctness of a classic slicing algorithm w.r.t. this.
Slides of the talk: [ pdf ]
Abstract: Optical graph recognition (OGR) is computer vision area that tries to detect graph topology from given raster image of graph drawing. Graph visualization techniques are so diverse that it requires to build specific recognizers depending on graph drawing style. Our approach allows to build graph recognizer algorithms interactively for a particular graph visualization class and seamlessly integrate produced algorithms into automated OGR systems.
Abstract: We address the problem of visualizing overlapping graph clustering in a comprehensible way. The presented graphical visualization algorithm generates an Euler diagram based on the graph clustering and a geometrical positioning of its vertices: for each cluster it defines a smooth curve bounding a planar region corresponding to the cluster; in the final result these shapes are colored according to the clusters they belong to. The presented approach works very well if the clusters intersect each other, a situation that often arises in social networks, producing regions that unambiguously reveal the structure of the clustering.
Slides of the talk: [ pdf ]
Abstract: This talk introduces the basics
of the two-party
secure computation protocols that are based on additive secret sharing.
The main focus is on the multiplication protocol which uses Paillier's
additively homomorphic cryptosystem and considerably differs from the
Sharemind's traditional three-party multiplication. We also consider
how to make the multiplication protocol more communication efficient by
packing several messages into one ciphertext. However, the proposed
multiplication protocol is relatively slow and we also consider using
it as a precomputation to enable fast online multiplication.
Full text paper : http://research.cyber.ee/reports/T-4-17-The-design-and-implementation-of-a-two-party-protocol-suite-for-Sharemind-3.pdf
Slides of the talk: [ pdf ]
Abstract: Quantum walks have been used for developing quantum algorithms that outperform their classical analogues. In the context of spatial search algorithms, quantum hitting time plays an important role as the algorithm's stopping time. We analyze a decoherence model on Szegedy's quantum walk, where random removal or insertions of edges in the graph can happen during the walk evolution. By performing averages over all possible evolution operators affected by the decoherence, we show that it is possible to define a decoherent quantum hitting time and to prove that the quadratic speedup for the quantum hitting time is still valid when the decoherence probability is small.
Slides of the talk: [ pptx ] [ pdf ]
Abstract: The goal of position-based
cryptography is to use
the geographic position of a party as its sole credential. A central
building block is the task of position-verification where a prover
wants to convince a set of verifiers that she is at a certain
geographical location. Protocols typically assume that messages can not
travel faster than the speed of light. By responding to a verifier in a
timely manner one can guarantee to be within a certain distance of that
verifier.
Quite recently it was shown that position-verification protocols only
based on this relativistic principle can be broken by two collaborating
attackers. Because of the no-cloning property of quantum information it
was believed that with the use of quantum messages one could devise
protocols that were resistant to such collaborative attacks.
However, recently, we could show that also in the quantum case no
unconditionally secure scheme is possible.
This talk is based on the following papers:
http://arxiv.org/abs/1009.2490
http://arxiv.org/abs/1109.2563
Slides of the talk: [ ppt ] [ pdf ]
Abstract:
Most known quantum algorithms can be expressed as query algorithms of
Boolean functions. The complexity of such algorithm is the worst-case
number of queries it makes to the input bits before determining the
value of the function. Van Dam in 1998 showed that a random Boolean
function can be computed, up to lower-order terms, with n/2 queries. In
1999 Ambainis showed that at least n/4 queries are needed by using the
just introduced polynomial method. Here we prove that the lower bound
actually coincides with the upper bound n/2, up to lower-order terms,
by a subtler usage of the same polynomial method.
Full text paper : http://arxiv.org/abs/1208.1122
Abstract: We attempt to improve the best known separation result between the degree and the sensitivity of a Boolean function. For this purpose we search for a 15-variable Boolean function of degree 5 and query complexity 15. We work with symmetrization polynomials which might correspond to a desired Boolean function. We study known, and propose new, relations between degree and sensitivity of a Boolean function and its symmetrization polynomial. We offer to repeatedly split symmetrization polynomials into polynomials of smaller size. We describe a set of conditions which must be met during this process. Using a computer program we prove no 15-variable Boolean function exists of degree 5 and sensitivity 15.
Abstract: Atoms of regular languages were
introduced in 2011.
An atom of a regular language L with n (left) quotients is a non-empty
intersection of uncomplemented or complemented quotients of L, where
each of the n quotients appears in a term of the intersection. Every
regular language defines a unique nondeterministic finite automaton
(NFA), atomaton, whose states are the atoms of the language. An NFA is
called atomic if the right languages of all its states are unions of
atoms. This talk will present some results obtained about atoms and
atomic NFAs. The first main result is a characterization of the class
of NFAs for which determinization by subset construction results in a
minimal DFA. It appears that this class consists of NFAs with atomic
reverse NFA. Second, we present a formula for the upper bound of
quotient complexity of any atom of L with r complemented quotients. For
each n?1, we exhibit a language whose atoms meet these bounds.
Full text papers:
DLT
2011 paper:DOI:10.1007/978-3-642-22321-1_10
DLT
2012 paper:DOI: 10.1007/978-3-642-31653-1_6
Abstract: Time vaults (a.k.a. timed-release encryption) are encryption schemes that allow the recipient to decrypt the message after a given, preconfigured time, but no earlier. One property that classical time vaults necessarily lack is the possibility to revoke the time vault. We show that due to the no-cloning property of quantum states, we can built quantum time vaults that can be revoked (with help of the recipient). That is, after sending a time vault to the recipient, the time vault can be returned to the sender, giving him the assurance that his message will stay secret forever.
Abstract: This talk is about certified programming, in dependently typed languages, of algorithms manipulating rational (or, regular) trees: the trees we consider can be infinitely deep (non-wellfounded), but constrained to have only a finite number of distinct subtrees. Trees like this are coinductive data that admit an inductive representation in the form of finite trees with back-pointers. Typical interesting properties of such data (bisimilarity etc.) are coinductive predicates, so a proof that a tree enjoys such a property would generally also be non-wellfounded. In some cases, we may limit our interest to non-wellfounded proofs with a finite number of distinct subproofs, representable as finite proofs with back-pointers. In this talk I will mostly discuss some examples, but also explain a bit of the category theory/type theory/proof theory background.
Abstract: In some situations state complexity of an automaton does not reflect the intuitive complexity of it - some automata with 21000 states can easily be modelled on a computer while some cannot. BC-complexity is an alternative complexity measure for finite automata - the transition function of an automaton is expressed as a Boolean circuit and complexity of this circuit is measured. Basic properties of BC-complexity will be stated in this presentation - its relation to the state complexity and Kolmogorov complexity, behaviour on the minimization operation and language operations.
Abstract: The sensitivity of a Boolean function f on a set S consisting of Boolean sequences of length n is the maximum sensitivity of f on an element of S. The problem addressed is to find the minimal possible size of such set with a maximum allowed sensitivity k, for a fixed value of f. It is known that the tight bound for the size of S is 2n-k elements. In this work, the sets studied must have some elements containing particular bit values on specified positions. The results include a bound for the minimal size of S and proofs on the optimality of this bound in some cases.
Slides of the talk: [ pptx ] [ pdf ]
Abstract: Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this talk, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS's for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca's). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be space efficient. As a further result, if the 2qcca can use a quantum counter instead of a classical one, then the protocol can even be public, also known as Arthur-Merlin games. We also investigate the computational power of 2pca's and 2qcca's as language recognizers. We show that bounded-error 2pca's can be more powerful than their deterministic counterparts by giving a bounded-error simulation of their nondeterministic counterparts. Then, we present a new programming technique for bounded-error 2qcca's and show that they can recognize a language which seems not to be recognized by any bounded-error 2pca. We also obtain some interesting results for bounded-error 1-pebble quantum finite automata based on this new technique. Lastly, we prove a conjecture posed by Ravikumar (FSTTCS 1992) regarding 1-pebble probabilistic finite automata, i.e. they can recognize some nonstochastic languages with bounded error.
Preprint: arXiv:1207.3880
Slides of the talk: [ ppt ]
Abstract: Reinforcement learning refers to the set of machine learning problems, solutions of which are mappings from states to actions computed with regard to some delayed reinforcement. There are a lot classical algorithms and methodologies for reinforcement learning problems (dynamic programming, sarsa, q-learning), typically based on the value-function approach, where values of the states are iteratively computed, and this set of values infers the policy. If a neural network or similar mechanism is used within such a system, it typically is delegated only with a subfunction, e.g., to model the table of state values. This work introduces a neural-network-based algorithm to solve reinforcement learning problems.