Source author record

Ariel Gabizon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Cryptography and Security Discrete Mathematics Formal Languages and Automata Theory Information Theory math.IT

Catalog footprint

Research overview

9works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Bitcoin Beacon

We examine a protocol $π_{\text{beacon}}$ that outputs unpredictable and publicly verifiable randomness, meaning that the output is unknown at the time that $π_{\text{beacon}}$ starts, yet everyone can verify that the output is close to uniform after $π_{\text{beacon}}$ terminates. We show that $π_{\text{beacon}}$ can be instantiated via Bitcoin under sensible assumptions; in particular we consider an adversary with an arbitrarily large initial budget who may not operate at a loss indefinitely. In case the adversary has an infinite budget, we provide an impossibility result that stems from the similarity between the Bitcoin model and Santha-Vazirani sources. We also give a hybrid protocol that combines trusted parties and a Bitcoin-based beacon.

preprint2016arXiv

On Probabilistic Checking in Perfect Zero Knowledge

We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and then engages with the prover in an Interactive Proof (IP). 2. The complexity class NEXP has PZK proofs in the model of Interactive Oracle Proofs (IOPs) [BCS16,RRR16], where the verifier, in every round of interaction, receives a PCP from the prover. Our constructions rely on succinct simulators that enable us to "simulate beyond NP", achieving exponential savings in efficiency over [BCGV16]. These simulators crucially rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: * An algorithm to detect constraints for Reed--Muller codes of exponential length. * An algorithm to detect constraints for PCPs of Proximity of Reed--Solomon codes [BS08] of exponential degree. The first algorithm exploits the Raz--Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. Along the way, we give a perfect zero knowledge analogue of the celebrated sumcheck protocol [LFKN92], by leveraging both succinct constraint detection and low-degree testing. The second algorithm exploits the recursive structure of the PCPs of Proximity to show that small-support constraints are "locally" spanned by a small number of small-support constraints.

preprint2015arXiv

Almost Optimal Cover-Free Families

Roughly speaking, an $(n,(r,s))$ -Cover Free Family (CFF) is a small set of $n$ -bit strings such that: "in any $d:=r+s$ indices we see all patterns of weight $r$ ". CFFs have been of interest for a long time both in discrete mathematics as part of block design theory, and in theoretical computer science where they have found a variety of applications, for example, in parametrized algorithms where they were introduced in the recent breakthrough work of Fomin, Lokshtanov and Saurabh under the name `lopsided universal sets'. In this paper we give the first explicit construction of cover-free families of optimal size up to lower order multiplicative terms, {for any $r$ and $s$ }. In fact, our construction time is almost linear in the size of the family. Before our work, such a result existed only for $r=d^{o(1)}$ . and $r= ω(d/(\log\log d\log\log\log d))$ . As a sample application, we improve the running times of parameterized algorithms from the recent work of Gabizon, Lokshtanov and Pilipczuk.

preprint2015arXiv

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation" variable, where the original problem corresponds to setting this variable to a constant value. For instance, the problem of packing sets of size at most $p$ into a given universe generalizes the Maximum Matching problem, which is recovered by taking $p=2$ . Most often, the complexity of the problem increases with the relaxation variable, but very recently Abasi et al. have given a surprising example of a problem --- $r$ -Simple $k$ -Path --- that can be solved by a randomized algorithm with running time $O^*(2^{O(k \frac{\log r}{r})})$ . That is, the complexity of the problem decreases with $r$ . In this paper we pursue further the direction sketched by Abasi et al. Our main contribution is a derandomization tool that provides a deterministic counterpart of the main technical result of Abasi et al.: the $O^*(2^{O(k \frac{\log r}{r})})$ algorithm for $(r,k)$ -Monomial Detection, which is the problem of finding a monomial of total degree $k$ and individual degrees at most $r$ in a polynomial given as an arithmetic circuit. Our technique works for a large class of circuits, and in particular it can be used to derandomize the result of Abasi et al. for $r$ -Simple $k$ -Path. On our way to this result we introduce the notion of representative sets for multisets, which may be of independent interest. Finally, we give two more examples of problems that were already studied in the literature, where the same relaxation phenomenon happens. The first one is a natural relaxation of the Set Packing problem, where we allow the packed sets to overlap at each element at most $r$ times. The second one is Degree Bounded Spanning Tree, where we seek for a spanning tree of the graph with a small maximum degree.

preprint2015arXiv

Subspace Polynomials and Cyclic Subspace Codes

Subspace codes have received an increasing interest recently due to their application in error-correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper we consider such cyclic codes and provide constructions of optimal codes for which their codewords do not have full orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes which are cyclic and analyze their parameters.

preprint2014arXiv

Deterministic Extractors for Additive Sources

We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both $\mathbb{Z}_p$ and $\mathbb{Z}_p^n$ , for large prime $p$ , although our results over $\mathbb{Z}_p^n$ require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over $\mathbb{Z}_p^n$ require the list-decodability condition. We further explore special cases of additive sources. We improve previous constructions of line sources (affine sources of dimension 1), requiring a field of size linear in $n$ , rather than $Ω(n^2)$ by Gabizon and Raz. This beats the non-explicit bound of $Θ(n \log n)$ obtained by the probabilistic method. We then generalize this result to APs and GAPs.

preprint2014arXiv

On $r$ -Simple $k$ -Path

An $r$ -simple $k$ -path is a {path} in the graph of length $k$ that passes through each vertex at most $r$ times. The $r$ -SIMPLE $k$ -PATH problem, given a graph $G$ as input, asks whether there exists an $r$ -simple $k$ -path in $G$ . We first show that this problem is NP-Complete. We then show that there is a graph $G$ that contains an $r$ -simple $k$ -path and no simple path of length greater than $4\log k/\log r$ . So this, in a sense, motivates this problem especially when one's goal is to find a short path that visits many vertices in the graph while bounding the number of visits at each vertex. We then give a randomized algorithm that runs in time $\mathrm{poly}(n)\cdot 2^{O( k\cdot \log r/r)}$ that solves the $r$ -SIMPLE $k$ -PATH on a graph with $n$ vertices with one-sided error. We also show that a randomized algorithm with running time $\mathrm{poly}(n)\cdot 2^{(c/2)k/ r}$ with $c<1$ gives a randomized algorithm with running time $\poly(n)\cdot 2^{cn}$ for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an $O(\log r)$ factor.

preprint2014arXiv

Relations between automata and the simple k-path problem

Let $G$ be a directed graph on $n$ vertices. Given an integer $k<=n$ , the SIMPLE $k$ -PATH problem asks whether there exists a simple $k$ -path in $G$ . In case $G$ is weighted, the MIN-WT SIMPLE $k$ -PATH problem asks for a simple $k$ -path in $G$ of minimal weight. The fastest currently known deterministic algorithm for MIN-WT SIMPLE $k$ -PATH by Fomin, Lokshtanov and Saurabh runs in time $O(2.851^k\cdot n^{O(1)}\cdot \log W)$ for graphs with integer weights in the range $[-W,W]$ . This is also the best currently known deterministic algorithm for SIMPLE k-PATH- where the running time is the same without the $\log W$ factor. We define $L_k(n)\subseteq [n]^k$ to be the set of words of length $k$ whose symbols are all distinct. We show that an explicit construction of a non-deterministic automaton (NFA) of size $f(k)\cdot n^{O(1)}$ for $L_k(n)$ implies an algorithm of running time $O(f(k)\cdot n^{O(1)}\cdot \log W)$ for MIN-WT SIMPLE $k$ -PATH when the weights are non-negative or the constructed NFA is acyclic as a directed graph. We show that the algorithm of Kneis et al. and its derandomization by Chen et al. for SIMPLE $k$ -PATH can be used to construct an acylic NFA for $L_k(n)$ of size $O^*(4^{k+o(k)})$ . We show, on the other hand, that any NFA for $L_k(n)$ must be size at least $2^k$ . We thus propose closing this gap and determining the smallest NFA for $L_k(n)$ as an interesting open problem that might lead to faster algorithms for MIN-WT SIMPLE $k$ -PATH. We use a relation between SIMPLE $k$ -PATH and non-deterministic xor automata (NXA) to give another direction for a deterministic algorithm with running time $O^*(2^k)$ for SIMPLE $k$ -PATH.

preprint2013arXiv

Improved Extractors for Affine Lines

Let $F$ be the field of $q$ elements. We investigate the following Ramsey coloring problem for vector spaces: Given a vector space $\F^n$, give a coloring of the points of $F^n$ with two colors such that no affine line (i.e., affine subspace of dimension $1$ ) is monochromatic. Our main result is as follows: For any $q\geq 25\cdot n$ and $n>4$ , we give an explicit coloring $D:F^n\ar \set{0,1}$ such that for every affine line $l\subseteq F^n$ , $D(l)=\set{0,1}$ . Previously this was known only for $q\geq c\cdot n^2$ for some constant $c$ \cite{GR05}. We note that this beats the random coloring for which the expected number of monochromatic lines will be 0 only when $q\geq c\cdot n\log n$ for some constant $c$ . Furthermore, our coloring will be `almost balanced' on every affine line. Let us state this formally in the lanuage of \emph{extractors}. We say that a function $D:F^n\mapsto \set{0,1}$ is a \afsext{1}{\eps} if for every affine line $l\subseteq \F^n$, $D(X)$ is $\eps$-close to uniform when $X$ is uniformly distributed over $l$ . We construct a \afsext{1}{\eps} with $\eps = Ω(\sqrt{n/q})$ whenever $q\geq c\cdot n$ for some constant $c$ . The previous result of \cite{GR05} gave a \afsext{1}{\eps} only for $q=Ω(n^2)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ariel Gabizon

Research overview

Is this your work?

9 publications

Bitcoin Beacon

On Probabilistic Checking in Perfect Zero Knowledge

Almost Optimal Cover-Free Families

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

Subspace Polynomials and Cyclic Subspace Codes

Deterministic Extractors for Additive Sources

On $r$ -Simple $k$ -Path

Relations between automata and the simple k-path problem

Improved Extractors for Affine Lines

See the researcher in context

Building this map preview

Ariel Gabizon

Research overview

Is this your work?

9 publications

Bitcoin Beacon

On Probabilistic Checking in Perfect Zero Knowledge

Almost Optimal Cover-Free Families

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

Subspace Polynomials and Cyclic Subspace Codes

Deterministic Extractors for Additive Sources

On rrr-Simple kkk-Path

Relations between automata and the simple k-path problem

Improved Extractors for Affine Lines

See the researcher in context

Building this map preview

On $r$ -Simple $k$ -Path