16 citations · 28 across the 9 of their papers we have counts for
11 papers
Twenty (simple) questions
Yuval Dagan, Yuval Filmus, Ariel Gabizon +1
A basic combinatorial interpretation of Shannon's entropy function is via the "20 questions" game. This cooperative game is played by two players, Alice and Bob: Alice picks a dist…
On Probabilistic Checking in Perfect Zero Knowledge
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes +3
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 com…
Bitcoin Beacon
Iddo Bentov, Ariel Gabizon, David Zuckerman
We examine a protocol that outputs unpredictable and publicly verifiable randomness, meaning that the output is unknown at the time that sta…
Almost Optimal Cover-Free Families
Nader H. Bshouty, Ariel Gabizon
Roughly speaking, an -Cover Free Family (CFF) is a small set of -bit strings such that: "in any indices we see all patterns of weight ". CFFs have been of…
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
Ariel Gabizon, Daniel Lokshtanov, Michal Pilipczuk
In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation"…
Deterministic Extractors for Additive Sources
Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê +1
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 arithmet…
Cryptocurrencies without Proof of Work
Iddo Bentov, Ariel Gabizon, Alex Mizrahi
We study decentralized cryptocurrency protocols in which the participants do not deplete physical scarce resources. Such protocols commonly rely on Proof of Stake, i.e., on mechani…
Subspace Polynomials and Cyclic Subspace Codes
Eli Ben-Sasson, Tuvi Etzion, Ariel Gabizon +1
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 possib…
Relations between automata and the simple k-path problem
Ran Ben-Basat, Ariel Gabizon
Let be a directed graph on vertices. Given an integer , the SIMPLE -PATH problem asks whether there exists a simple -path in . In case is weighted, the M…
On -Simple -Path
Hasan Abasi, Nader H. Bshouty, Ariel Gabizon +1
An -simple -path is a {path} in the graph of length that passes through each vertex at most times. The -SIMPLE -PATH problem, given a graph as input, asks w…
Improved Extractors for Affine Lines
Ariel Gabizon
Let be the field of elements. We investigate the following Ramsey coloring problem for vector spaces: Given a vector space $\F^n$, give a coloring of the points of wi…