All reports by Author Eylon Yogev:

__
TR19-169
| 21st November 2019
__

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 2

__
TR18-213
| 28th December 2018
__

Moni Naor, Merav Parter, Eylon Yogev#### The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

__
TR17-015
| 4th February 2017
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Revisions: 1

__
TR16-199
| 15th December 2016
__

Pavel Hubacek, Moni Naor, Eylon Yogev#### The Journey from NP to TFNP Hardness

__
TR16-063
| 18th April 2016
__

Pavel Hubacek, Eylon Yogev#### Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Revisions: 1

__
TR16-023
| 23rd February 2016
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### How to Share a Secret, Infinitely

Revisions: 4

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are ``exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

Moni Naor, Merav Parter, Eylon Yogev

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

Pavel Hubacek, Moni Naor, Eylon Yogev

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

Pavel Hubacek, Eylon Yogev

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best ... more >>>