[ Homepage ] [ Koduleht ] [ Mājaslapa ]
Slides of the talk: [ pdf ]
Abstract: Discrete objects (concepts) are an illusion in the multidimensional neural minds of the higher animals and humans. Word embeddings [Mikolov, 2013: word2vec] derived in unsupervised manner from the large text corpora show that words (concepts) can be mapped to points (vectors) in the high-dimensional space so that the similar concepts appear closer than dissimilar ones and semantic relationships like $King-Man+Woman=Queen$ hold for word-vectors in the embedding space. However, the precise reason for such semantically perfect arithmetic properties of word embedding vectors remain elusive. Here we propose that the word embedding arithmetic properties are a byproduct of the compositional nature of the concepts appearing in the natural language. We speculate that word-vectors are the sum of (nearly-)orthogonal high-dimensional vectors representing their semantic components and therefore the orthogonality of the discrete semantic components rather than continuous (differentiable) geometry of the embedding space itself is driving both the similar concept proximity and arithmetic relationships in the embedding space.
Abstract:
In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this talk we study query complexity of epsilon-testing monotonicity of a function $f : [n]\rightarrow[r]$.
Our results are two-fold:
* We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $\Omega((\log r)/(\log\log r))$ when $\epsilon = 1/2$. No previous satisfactory lower bound in terms of r was known.
* We completely characterise query complexity of this problem in terms of $n$ for smaller values of epsilon. The complexity is $\Theta(\epsilon^{-1} \log (\epsilon n))$. Apart from giving the lower bound, this improves on the best known upper bound.
Slides of the talk: [ pdf ]
Abstract:
A real-valued function f defined on a semigroup is subadditive if $f(xy) \leq f(x) + f(y)$ for every $x$ and $y$. Subadditivity appears in several contexts and is at the basis of results of great relevance, such as Fekete's lemma for functions defined on the positive integers or positive reals, or the Ornstein-Weiss lemma for amenable groups.
In this talk, extending the arguments in Einar Hille's 1948 textbook, I will describe the general properties of subadditive functions and discuss some special cases. I will then introduce a different setting, where a function of many variables is subadditive in each one, given the others, and discuss how to extend Fekete's lemma to the new case.
Slides of the talk: [ pdf ]
Abstract: We investigate interactive proof systems (IPSs) with probabilistic verifiers and provers and consider the verification of every language. The task of the verifier is to make a decision on a given input by interacting with provers. We show that for any language, there is a constant-space IPS with two provers where the verifier reads the input once. The result is based on the algorithm proposed by Feige and Shamir: the constant-space verifier uses cryptographic approach for the interaction with two provers to reliably simulate the infinite work tape. During the talk we will present all steps of the protocol. We will also mention our results for IPSs with one prover: for any unary (binary) language, there is a log-space (linear-space) IPS; for any language, there is a constant-space weak-IPS (the non-members may not be rejected with high probability). Additionally, we show that uncountably many binary (unary) languages can be verified in constant space and in linear (quadratic) expected time. The talk is based on our paper "Probabilistic verification of all languages" (https://arxiv.org/abs/1807.04735).
Slides of the talk: [ pdf ]
Abstract: We introduce a frequentist semantics for conditionalization on partially known events. This notion of probability is conditional on a list of event-probability specifications, and we denote it as $P(A|B1:=b1,...,Bn:=bn)$. We call it frequentist partial (F.P.) conditionalization. As in Jeffrey conditionalization, a specification pair $B:=b$ stands for the assumption that the probability of B has somehow changed from a previously given, a priori probability into a new, a posteriori probability. We give a formal, frequentist semantics to this kind of conditionalization. We think of conditionalization as taking place in chains of repeated experiments, so-called probability testbeds, of sufficient lengths. We prove that F.P. conditionalization meets Jeffrey conditionalization. Jeffrey conditionalization treats the special case of partitions, i.e., the case in which all of the events are mutually disjoint and sum up to a probability of 100%. With our semantics, these requirements can be dropped so that we can deal with arbitrary lists of overlapping events. This way, F.P. conditionalization generalizes Jeffrey conditionalization, opening it for reassessment and a range of potential applications. The postulate of Jeffrey's probability kinematics, which is rooted in the subjectivism of Frank P. Ramsey, turns out to be a consequence in our frequentist semantics. This way, F.P. conditionalization bridges between the Kolmogorov system of probability and one of the important Bayesian frameworks.
Slides of the talk: [ pptx ]
Abstract: Preference aggregation is a challenging task: Arrow’s famous impossibility theorem tells us that there is no perfect voting rule. One of the best-known ways to circumvent this difficulty is to assume that voters’ preferences satisfy a structural constraint, such as, e.g., being single-peaked. Indeed, under this assumption many impossibility results in social choice disappear. Restricted preference domains also play an important role in computational social choice: for instance, there are voting rules that are NP-hard to compute in general, but admit efficient winner determination algorithms when voters’ preferences belong to a restricted domain. However, restricted domains that have nice social choice-theoretic properties are not necessarily attractive from an algorithmic perspective, and vice versa. In this note, we will discuss some domain restrictions that have proved to be useful from a computational perspective, and compare the use of restricted domains in computational and classic social choice theory.
Slides of the talk: [ pptx ]
Abstract: Algorithm learning is a core problem in artificial intelligence with significant implications on automation level that can be achieved by machines. Recently deep learning(DL) methods are emerging for synthesizing an algorithm from its input-output examples the most successful being the Neural GPU, capable of learning multiplication. In this talk we will review these methods and present our work for making an improved architecture. We have introduced several improvements to the Neural GPU that substantially reduces training time and improves generalization. The proposed architecture is the first capable of learning decimal multiplication end-to-end. We will also discuss our work in progress how to learn faster algorithms - for example sorting running in $O(\log^2 n)$ parallel time.
Abstract: In algebraic coding theory, the BCH bound is probably one of the most impressive examples, showing how a Fourier transform can be used in order to construct codes of prescribed minimum distance. So far, this spectral technique is basically restricted to cyclic codes, however there is no strong reason to keep it restricted to this case. This talk is particularly interested in the scenario, where a non-commutative finite group describes the co-ordinate domain. We will sketch the successful development of a Fourier theory for this setting and observe a few strange facts.
Abstract: We investigate an highly performant fully homomorphic encryption scheme that uses one-time keys and one-time programs. The scheme might be also applicable in white-box cryptography, if the one-time keys are disclosed partially.
Slides of the talk: [ pdf ]
Abstract: The past couple of years have seen significant developments in physical quantum computing devices, and several have become accessible to the wider public. Although these are still noisy small-scale devices, experiments on them can offer insights into some of the challenges and opportunities of near-term quantum computing. This talk offers a summary of the functionality of IBM Quantum Experience and Rigetti physical quantum computers, presented through a partial implementation of a space-efficient quantum finite automaton by Ambainis and Freivalds, improved by Ambainis and Nahimovs. Although it is not possible to fully implement this quantum finite automaton on any of the currently available physical devices, some of its aspects can be implemented. The quality of results depends substantially on the number of two-qubit gates and the quality of the physical qubits used.
Abstract: We study probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. These probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor $\langle 2,2,2 \rangle$ that represents $2\times 2$ matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank of $\langle 2,2,2 \rangle$ is $7$ [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)] we show that the probabilistic rank of $\langle 2,2,2 \rangle$ is at most $6+\frac{6}{7}$ and the probabilistic border rank is at most $6+\frac{2}{3}$. By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs.
Slides of the talk: [ pdf ]
Abstract: In this paper, we present Quantum Dynamic Programming approach for problems on directed acycling graphs (DAGs). The algorithm has the time complexity $O(\sqrt{\hat{n}m}\log \hat{n})$ comparing to a deterministic one that has the time complexity $O(n+m)$. Here $n$ is a number of vertexes, $\hat{n}$ is a number of vertexes with at least one outgoing edge; and $m$ is a number of edges. We show that we can solve problems that have OR, AND, NAND, MAX and MIN functions as the main transition step. The approach is useful for a couple of problems. One of them is computing Boolean formula that represented by DAG with AND and OR boolean operations in vertexes. Another one is DAG's diameter search, Shortest path search and longest path search.
Abstract:
We study variations of the well-known Nim game. In our game two players operate with only one heap of $n$ stones. The rules are defined by $n(n+1)/2$ bits which determine allowed number of stones which a player can remove from the heap of a given size. Let $A_{j,i}=1$ iff a player can remove $i$ stones once there remain exactly $j$ stones in the heap ($i\le j$). One who cannot make a legal move loses, and their opponent wins the game.
The best known deterministic algorithms for solving such games are based on the dynamic programming approach. The main idea of the method is solving a game using precomputed solutions for the same game, but with smaller numbers of stones in the heap. We construct directed acyclic graph (DAG) of all $n+1$ positions of the game (each position corresponds to the number of remaining stones, and each edge corresponds to a valid move). Then we mark each vertex with all outgoing edges to ``winning'' vertices as ``losing'' vertex, and mark each vertex with an outgoing edge to a ``losing'' vertex as ``winning'' vertex. The last step is repeated until all $n+1$ vertices are marked, and then the value of the game corresponds to the root vertex ``$n$''. Dynamic programming on DAGs uses Depth-first search algorithm (DFS) as a subroutine [cormen2001]. Thus, this algorithm has at least time complexity of DFS, that is $O(n+m)$, where $m$ is the number of edges and $n$ is the number of vertices.
We suggest a quantum algorithm with time complexity $O(\sqrt{\hat{n}m}\log \hat{n})=O(\sqrt{\hat{n}m}\log \hat{n})=O(\sqrt{nm}\log n)$, where $\hat{n}$ is the number of vertices with non-zero outgoing degree. We reach the declared time complexities in the case of using adjacency list for storing the graph. If the adjacency matrix is used, then the time complexity is $O(n\sqrt{\hat{n}}\log \hat{n})=O(n^{1.5}\log n)$. In the classical case using this data structure results in time complexity $O(n^2)$.
Slides of the talk: [ pdf ]
Abstract: The genus of a graph G is the minimum number of handles needed in a surface, so that it is possible to embed the graph without edges crossing. For example the planar graphs have genus 0 and the graphs that can be "drawn" on a torus have genus 1. I will discuss an interesting question about modelling road junctions, that motivated finding the genus of complete tripartite graphs $K_{n,n,1}$.
Slides of the talk: [ odp ]
Abstract: The sensitivity of a function is the maximum change of its output for a unit change of its input. In this paper we present a method for determining the sensitivity of SQL queries, seen as functions from databases to datasets, where the change is measured in the number of rows that differ. Given a query, a database schema and a number, our method constructs a formula that is satisfiable only if the sensitivity of the query is bigger than this number. Our method is composable, and can also be applied to SQL workflows. Our results can be used to calibrate the amount of noise that has to be added to the output of the query to obtain a certain level of differential privacy.
Slides of the talk: [ pdf ]
Abstract:
As the halting problem is generally undecidable, different methods have been proposed in the literature for termination analysis of programs under some extra restrictions. We investigate the termination problem of quantum programs and obtain positive results by extending some of the classical methods into the quantum case. For finite-dimensional quantum programs, we prove by a quantum generalization of the 0-1 law that the termination problem is decidable. For infinite-dimensional quantum programs, we analyze the termination by introducing the notion of linear ranking super-martingale (LRSM), and then use Semi-Definite Programming to solve the synthesis problem of LRSMs. This is essentially
a generalization of the constraint-based approach to the corresponding problems for probabilistic programs developed in the recent literature by adding two novel ideas: (1) employing the Gleason’s theorem in quantum mechanics to guide the choices of templates; and (2) a generalised Farkas’ lemma in terms of Hermitian operators.
Slides of the talk: [ pptx ]
Abstract: While the CRS model is widely accepted for construction of non-interactive zero knowledge (NIZK) proofs, from the practical viewpoint, a very important question is to minimize the trust needed from the creators of the CRS. Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. First, we observe that subversion zero knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK (also known as nonuniform NIZK) in the Bare Public Key (BPK) model. Due to well-known impossibility results, this observation provides a simple proof that the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is nonuniform zero knowledge in the BPK model under two alternative novel knowledge assumptions, both secure in the subversion generic bilinear group model. We prove that (for a different set of parameters) a slightly less efficient variant of Kiltz-Wee is nonuniform zero knowledge in the BPK model under a known knowledge assumption that is also secure in the subversion generic bilinear group model.
Abstract: In this talk, we present our recent results on probabilistic finite automata (PFAs) and unary quantum finite automata (uQFAs) having only two states. We showed that, for any fixed cutpoint $\lambda\in(0,1)$, uncountably many 2-state PFAs can be constructed in a way that any two of them recognize di erent languages with cutpoint $\lambda$. Therefore, 2-state PFAs can recognize uncountably many languages with a fixed cutpoint. Then, we considered 2-state uQFAs with cutpoint $1/2$ and obtained a similar result: 2-state uQFAs, which simply rotate on the unit circle defined on $R^2$, recognize uncountably many languages with fixed cutpoint $1/2$. Here, we showed that for each pair of rotations of the form $2\pi\alpha$ such that $\alpha \in [0,1/4]$, we can always find a string that can be recognized by one of the corresponding uQFAs and cannot be recognized by the other one with cutpoint $1/2$.
Slides of the talk: [ pdf ]
Abstract: We present improved protocols for the conversion of secret-shared bit-vectors into secret-shared integers and vice versa, for the use as subroutines in secure multiparty computation (SMC) protocols and for protocols verifying the adherence of parties to prescribed SMC protocols. The protocols are primarily designed for three-party computation with honest majority. We evaluate our protocols as part of the Sharemind three-party protocol set and see a general reduction of verification overheads, thereby increasing the practicality of covertly or actively secure Sharemind protocols.
Slides of the talk: [ pdf ]
Abstract: We study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $\tilde{O}(1.817^n)$. The technique combines Grover’s search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $\tilde{O}(1.817^n)$, and graph bandwidth in time $\tilde{O}(2.946^n)$. Then we use similar ideas to solve the traveling salesman problem and minimum set cover in time $\tilde{O}(1.728^n)$.
Slides of the talk: [ pdf ]
Abstract: We will apply a construction of hypergraphs by Erdős, Frankl and Rödl satisfying a girth condition in order to construct batch codes and PIR codes with good properties. Batch codes can be applied to store hot data on multiple servers with good reliability and accessibility properties. PIR codes can be applied to multi-server private information retrieval as a coding layer to reduce the storage overhead. Our batch (and PIR) codes, in addition to having low redundancy, can be applied in asynchronous access to data, as opposed to for example simplex codes that are good batch codes only in the synchronous model. This is joint work with Vitaly Skachek and Eldho K. Thomas, to be published in the ITW 2018 conference in Guangzhou, China.
Slides of the talk: [ pptx ]
Abstract:
In state-of-the-art e-voting systems, a bulletin board (BB) is a critical component for preserving election integrity and availability. We introduce a framework for the formal security analysis of the BB functionality modeled as a distributed system. Our framework treats a secure BB as a robust public transaction ledger, defifined by Garay et al. [Eurocrypt 2015], that additionally supports the generation of receipts for successful posting. Namely, in our model, a secure BB system achieves
Persistence and Liveness that can be confifirmable, in the sense that any malicious behavior can be detected via a verifification mechanism.
As a case study for our framework, we analyze security guarantees and weaknesses of the BB system of [CSF 2014]. We demonstrate an attack revealing that the said system does not achieve Confifirmable Liveness in our framework, even against covert adversaries. In addition, we show that special care should be taken for the choice of the underlying cryptographic primitives, so that the claimed fault tolerance threshold of $N/3$ out-of $N$ corrupted IC peers is preserved.
Next, based on our analysis, we introduce a new BB protocol that upgrades the [CSF 2014] protocol. We prove that it tolerates any number less than $N/3$ out-of $N$ corrupted IC peers both for Persistence and Confifirmable Liveness, against a computationally bounded general Byzantine adversary. Furthermore, Persistence can also be Confifirmable, if we distribute the AB (originally a centralized entity in [CSF 2014]) as a replicated service with honest majority.
Abstract:
A new decoding algorithm for Low-Density Parity-Check (LDPC) codes on the Additive White Gaussian Noise (AWGN) channel is proposed. The algorithm is based on the idea of using redundant parity checks and additional variable nodes. The new key element in the proposed algorithm is the use of the orthogonal subsets of parity checks for computing soft decisions for different variable nodes. This allows for significant improvement in the decoding error performance of the algorithm compared to the known counterparts. Furthermore, new bounds on the error performance of the BP decoding applied to the parity-check matrices with redundant parity-checks are obtained.
Based on this paper: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8437588
Abstract: Quantum Hoare logic allows us to reason about the properties of quantum programs: given what precondition, what postcondition will hold. However, there are some things that today's Hoare logics cannot express properly, e.g., that a variable has classical content, or that some value is uniformly distributed. We present (early work on) a quantum Hoare Logic with "ghost variables". These are variables that do not occur in the program and are added purely to increase the expressivity of predicates. This allows us to encode facts such as "x is classical" or "x is uniformly distributed". With such predicates, we can, e.g., analyse the quantum one-time pad.