We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity. This achieves parameters that surpass all previously known PCPs and IOPs. Specifically, we construct an IOP with perfect completeness, soundness error $1 / n$, round complexity $O(\log \log n)$, proof length poly $(n)$ over an alphabet of size $O(n)$, and query complexity $O(\log \log n)$. This is a step forward in the quest to establish the sliding-scale conjecture for IOPs (which would additionally require query complexity $O(1))$. Our main technical contribution is a high-soundness small-query proximity test for the Reed-Solomon code. We construct an IOP of proximity for Reed-Solomon codes, over a field $\mathbb{F}$ with evaluation domain L and degree d, with perfect completeness, soundness error (roughly) $\max \{1-\delta, O(\rho^{1 / 4})\}$ for $\delta$-far functions, round complexity $O(\log \log d)$, proof length $O(|L| / \rho)$ over $\mathbb{F}$, and query complexity $O(\log \log d)$; here $\rho=(d+1) /|L|$ is the code rate. En route, we obtain a new high-soundness proximity test for bivariate Reed-Muller codes.The IOP for NP is then obtained via a high-soundness reduction from NP to Reed-Solomon proximity testing with rate $\rho=1 / \operatorname{poly}(n)$ and distance $\delta=1-1 / \operatorname{poly}(n)$ (and applying our proximity test). Our constructions are direct and efficient, and hold the potential for practical realizations that would improve the state-of-the-art in real-world applications of IOPs.

SPHINCS+ [CCS ’19] is one of the selected post-quantum digital signature schemes of NIST’s post-quantum standardization process. The scheme is a hash-based signature and is considered one of the most secure and robust proposals. The proposal includes a fast (but larger) variant and a small (but slower) variant for each security level. The main problem that might hinder its adoption is its large signature size. Although SPHINCS+ supports a trade-off between signature size and the computational cost of signing, further reducing the signature size (below the small variants) results in a prohibitively high computational cost for the signer.This paper presents several novel methods for further compressing the signature size while requiring negligible added computational costs for the signer and further reducing verification time. Moreover, our approach enables a much more efficient trade-off curve between signature size and the computational costs of the signer. In many parameter settings, we achieve small signatures and faster running times simultaneously. For example, for 128-bit (classical) security, the small signature variant of SPHINCS+ is 7856 bytes long, while our variant is only 6304 bytes long: a compression of approximately 20% while still reducing the signer’s running time. However, other trade-offs that focus, e.g., on verification speed, are possible.The main insight behind our scheme is that there are predefined specific subsets of messages for which the WOTS+ and FORS signatures (that SPHINCS+ uses) can be compressed, and generation can be made faster while maintaining the same security guarantees. Although most messages will not come from these subsets, we can search for suitable hashed values to sign. We sign a hash of the message concatenated with a counter that was chosen such that the hashed value is in the subset. The resulting signature is both smaller and faster to sign and verify.Our schemes are simple to describe and implement. We provide an implementation, a theoretical analysis of speed and security, as well as benchmark results.

The Exponential-Time Hypothesis (ETH) is a strengthening of the 𝒫 ≠ 𝒩𝒫 conjecture, stating that 3- SAT on n variables cannot be solved in (uniform) time 2 εċ n , for some ε > 0. In recent years, analogous hypotheses that are “exponentially strong” forms of other classical complexity conjectures (such as 𝒩𝒫⊈ ℬ𝒫𝒫 or co 𝒩𝒫⊈𝒩𝒫) have also been introduced and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely related questions of derandomization and circuit lower bounds . We show that even relatively mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: (1) The Randomized Exponential-Time Hypothesis (rETH) implies that ℬ𝒫𝒫 can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i.e., in time 2 Õ(log( n )) = n loglog( n ) O(1) ). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i.e., with seed length Õ(log ( n ))); this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. (2) The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of ℬ𝒫𝒫 is completely equivalent to circuit lower bounds against ℰ, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Last, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CircuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2 n /polylog(n) , then ℬ𝒫ℰ does not have circuits of quasilinear size.

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally F p -estimation, F p -heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+ε)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n , 1/ε) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.

Abstract. A program obfuscator takes a program and outputs a “scrambled” version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. [Advances in Cryptology - CRYPTO, 2001, Lect. Notes Comput. Sci. 2139, Springer, Berlin, Heidelberg, pp. 1–18], the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. In 2013, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. [Proceedings of the Symposium on Theory of Computing Conference, STOC, ACM, 2013, pp. 467–476]. This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters [Proceedings of the Symposium on Theory of Computing, 2014, STOC, pp. 475–484]). Most of them explicitly rely on additional hardness assumptions, such as one-way functions. Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if [Formula: see text], then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if [Formula: see text] and program obfuscation is possible, then one-way functions exist. Our main result is that if [Formula: see text] and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for [Formula: see text]. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the-average [Formula: see text] problems. To get some of our results we need obfuscators for simple programs such as [Formula: see text] circuits.

Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone’s dimension, thus resolving the main open question from Ben-David, Pál, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).

The Exponential-Time Hypothesis (ETH) is a strengthening of the P ≠ NP conjecture, stating that 3-SAT on n variables cannot be solved in (uniform) time 2ε·n, for some . In recent years, analogous hypotheses that are “exponentially-strong” forms of other classical complexity conjectures (such as NP ⊄ eq BPP or coNP ⊄ eq NP) have also been introduced, and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely-related questions of derandomization and circuit lower bounds. We show that even relatively-mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: 1) The Randomized Exponential-Time Hypothesis (rETH) implies that BPP can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i.e., in time 2~O(log(n))=nloglog(n)O(1)). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i.e., with seed length ~O(log(n))); this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. 2) The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of BPP is completely equivalent to circuit lower bounds against E, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Lastly, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CireuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2n/polylog(n), then BPε does not have circuits of quasilinear size.

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally $F_p$-estimation, Fp-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+ε)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n, 1/ε) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.

Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet "representative" subset of the data. In this work, we investigate the robustness of sampling against adaptive adversarial attacks in a streaming setting: An adversary sends a stream of elements from a universe U to a sampling algorithm (e.g., Bernoulli sampling or reservoir sampling), with the goal of making the sample "very unrepresentative" of the underlying data stream. The adversary is fully adaptive in the sense that it knows the exact content of the sample at any given point along the stream, and can choose which element to send next accordingly, in an online manner. Well-known results in the static setting indicate that if the full stream is chosen in advance (non-adaptively), then a random sample of size Ω(d/ε2) is an ε-approximation of the full data with good probability, where d is the VC-dimension of the underlying set system (U, R). Does this sample size suffice for robustness against an adaptive adversary? The simplistic answer is negative : We demonstrate a set system where a constant sample size (corresponding to a VC-dimension of 1) suffices in the static setting, yet an adaptive adversary can make the sample very unrepresentative, as long as the sample size is (strongly) sublinear in the stream length, using a simple and easy-to-implement attack. However, this attack is "theoretical only", requiring the set system size to (essentially) be exponential in the stream length. This is not a coincidence: We show that in order to make the sampling algorithm robust against adaptive adversaries, the modification required is solely to replace the VC-dimension term d in the sample size with the cardinality term log |R|. That is, the Bernoulli and reservoir sampling algorithms with sample size Ω(log |R|/ε2) output a representative sample of the stream with good probability, even in the presence of an adaptive adversary. This nearly matches the bound imposed by the attack.

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 graph G belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size. This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of noninteractive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism – both of which require proofs of Ω(n2)-bits without interaction. In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier. We show the following: Every (centralized) computation performed in time O(n) on a RAM can be translated into three-round distributed interactive protocol with O(log n) proof size. This implies that many graph problems for sparse graphs have succinct proofs (e.g., testing planarity). Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with O(1) rounds and O(log n) bits proof size for the low space case and polylog(n) many rounds and proof size for NC. We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with O(log n) proof size, improving upon the O(n log n) proof size of Kol et al. For many problems, we show how to reduce proof size below the seemingly natural barrier of log n. By employing our RAM compiler, we get a 5-round protocol with proof size O (log log n) for a family of problems including Fixed Automorphism, Clique and Leader Election (for the latter two problems we actually get O(1) proof size). Finally, we discuss how to make these proofs noninteractive arguments via random oracles. Our compilers capture many natural problems and demonstrate the difficulty in showing lower bounds in these regimes.

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 problem is defined by a continuous function which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class ${CLS}$ [C. Daskalakis and C. H. Papadimitriou, Proceedings of SODA'11, 2011], which is contained in the intersection of ${PLS}$ and ${PPAD}$, two important subclasses of ${TFNP}$ (the class of ${NP}$ search problems with a guaranteed solution). In this work, we show the first hardness results for ${CLS}$ (the smallest nontrivial class among the currently defined subclasses of $\mathbf{TFNP}$). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions. Our results demonstrate a strong conceptual barrier precluding design of efficient algorithms for solving local search problems even over continuous domains. As our main technical contribution we introduce a new total search problem which we call End-of-Metered-Line. The special structure of End-of-Metered-Line enables us to (1) show that it is contained in ${CLS}$, (2) prove hardness for it in both the black-box and the white-box setting, and (3) extend to ${CLS}$ a variety of results previously known only for ${PPAD}$.

Short cycle decomposition is an edge partitioning of an unweighted graph into edge-disjoint short cycles, plus a small number of extra edges not in any cycle. This notion was introduced by Chu et al. [FOCS'18] as a fundamental tool for graph sparsification and sketching. Clearly, it is most desirable to have a fast algorithm for partitioning the edges into as short as possible cycles, while omitting few edges. The most naïve procedure for such decomposition runs in time O(m * n) and partitions the edges into O(log n)-length edge-disjoint cycles plus at most 2n edges. Chu et al. improved the running time considerably to m^{1+o(1)}, while increasing both the length of the cycles and the number of omitted edges by a factor of n^{o(1)}. Even more recently, Liu-Sachdeva-Yu [SODA'19] showed that for every constant delta in (0,1] there is an O(m * n^{delta})-time algorithm that provides, w.h.p., cycles of length O(log n)^{1/delta} and O(n) extra edges. In this paper, we significantly improve upon these bounds. We first show an m^{1+o(1)}-time deterministic algorithm for computing nearly optimal cycle decomposition, i.e., with cycle length O(log^2 n) and an extra subset of O(n log n) edges not in any cycle. This algorithm is based on a reduction to low-congestion cycle covers, introduced by the authors in [SODA'19]. We also provide a simple deterministic algorithm that computes edge-disjoint cycles of length 2^{1/epsilon} with n^{1+epsilon}* 2^{1/epsilon} extra edges, for every epsilon in (0,1]. Combining this with Liu-Sachdeva-Yu [SODA'19] gives a linear time randomized algorithm for computing cycles of length poly(log n) and O(n) extra edges, for every n-vertex graphs with n^{1+1/delta} edges for some constant delta. These decomposition algorithms lead to improvements in all the algorithmic applications of Chu et al. as well as to new distributed constructions.

In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.

In Recommender Systems research, algorithms are often characterized as either Collaborative Filtering (CF) or Content Based (CB). CF algorithms are trained using a dataset of user preferences while CB algorithms are typically based on item profiles. These approaches harness different data sources and therefore the resulting recommended items are generally very different. This paper presents the CB2CF, a deep neural multiview model that serves as a bridge from items content into their CF representations. CB2CF is a "real-world" algorithm designed for Microsoft Store services that handle around a billion users worldwide. CB2CF is demonstrated on movies and apps recommendations, where it is shown to outperform an alternative CB model on completely cold items.

A cycle cover of a bridgeless graph G is a collection of simple cycles in G such that each edge e appears on at least one cycle. The common objective in cycle cover computation is to minimize the total lengths of all cycles. Motivated by applications to distributed computation, we introduce the notion of low-congestion cycle covers, in which all cycles in the cycle collection are both short and nearly edge-disjoint. Formally, a (d, c)-cycle cover of a graph G is a collection of cycles in G in which each cycle is of length at most d and each edge participates in at least one cycle and at most c cycles. A-priori, it is not clear that cycle covers that enjoy both a small overlap and a short cycle length even exist, nor if it is possible to efficiently find them. Perhaps quite surprisingly, we prove the following: Every bridgeless graph of diameter D admits a (d, c)-cycle cover where d = Õ(D) and c = Õ(1). That is, the edges of G can be covered by cycles such that each cycle is of length at most Õ(D) and each edge participates in at most Õ(1) cycles. These parameters are existentially tight up to polylogarithmic terms. Furthermore, we show how to extend our result to achieve universally optimal cycle covers. Let Ce is the shortest cycle that covers e, and let OPT(G) = maxe∊G |Ce|. We show that every bridgeless graph admits a (d, c)-cycle cover where d = Õ(OPT(G)) and c = Õ(1). We demonstrate the usefulness of low congestion cycle covers in different settings of resilient computation. For instance, we consider a Byzantine fault model where in each round, the adversary chooses a single message and corrupt in an arbitrarily manner. We provide a compiler that turns any r-round distributed algorithm for a graph G with diameter D, into an equivalent fault tolerant algorithm with r·poly(D) rounds.

In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information (e.g., distributed networks of selfish agents, decentralized digital currency such as Bitcoin). While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptographic community. The existing secure MPC protocols do not quite fit the framework of classical distributed models in which only messages of bounded size are sent on graph edges in each round. In this paper, we introduce a new framework for secure distributed graph algorithms and provide the first general compiler that takes any “natural” non-secure distributed algorithm that runs in r rounds, and turns it into a secure algorithm that runs in Õ(r · D · poly(Δ)) rounds where Δ is the maximum degree in the graph and D is its diameter. A “natural” distributed algorithm is one where the local computation at each node can be performed in polynomial time. An interesting advantage of our approach is that it allows one to decouple between the price of locality and the price of security of a given graph function f. The security of the compiled algorithm is information-theoretic but holds only against a semi-honest adversary that controls a single node in the network. This compiler is made possible due to a new combinatorial structure called private neighborhood trees: a collection of n trees T(u1), …, T(un), one for each vertex ui ∊ V(G), such that each tree T(ui) spans the neighbors of ui without going through ui. Intuitively, each tree T(ui) allows all neighbors of ui to exchange a secret that is hidden from ui, which is the basic graph infrastructure of the compiler. In a (d, c)-private neighborhood trees each tree T(ui) has depth at most d and each edge e ∊ G appears in at most c different trees. We show a construction of private neighborhood trees with d = Õ(Δ · D) and c = Õ(D), both these bounds are existentially optimal.

We study parallel algorithms for the classical balls-into-bins problem, in which m balls acting in parallel as separate agents are placed into n bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+Θ(\sqrtm/n\cdot łog n )$ (for $m\geq n łog n$) with high probability (w.h.p.). In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(łogłog m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(łogłog (m/n)+łog^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(łog^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $Ømega(\min\łogłog (m/n),n\ )$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(łog n)$ messages w.h.p. This goes to show that, similar to the case of $m=n$, asymmetry allows for highly efficient solutions.

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 while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision-resistant hash function exists (which follows from the hardness of problems such as factoring, discrete-log, and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. This is also true for the colorful Ramsey problem where one is looking, say, for a monochromatic triangle. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is that of succinct black-box, where the complexity of an algorithm is measured as a function of the description size of the object in the box (and no limitation on the computation time). In this case, we show that for all TFNP problems there is an efficient algorithm with complexity proportional to the description size of the object in the box times the solution size. However, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property that is hard to test even when one is given the program for computing the graph (under the appropriate assumptions such as hardness of Decisional Diffie-Hellman). The hard property is whether the graph is a two-source extractor.

Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the adversarial model . Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, we consider a data structure known as a “Bloom filter” and prove a tight connection between Bloom filters in this model and cryptography. A Bloom filter represents a set S of elements approximately by using fewer bits than a precise representation. The price for succinctness is allowing for some errors: For any x ∈ S , it should always answer Yes, and for any x ∉ S it should answer Yes only with small probability. In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the number of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries, we show that there exists a Bloom filter for sets of size n and error ε that is secure against t queries and uses only O ( n log 1/ε + t ) bits of memory. In comparison, n log 1/ε is the best possible under a non-adaptive adversary.

Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide range of applications ranging from distance oracles, labeling schemes and routing to solving linear systems and spectral sparsification. A $k$-spanner maintains pairwise distances up to multiplicative factor of $k$. It is a folklore that for every $n$-vertex graph $G$, one can construct a $(2k-1)$ spanner with $O(n^{1+1/k})$ edges. In a distributed setting, such spanners can be constructed in the standard CONGEST model using $O(k^2)$ rounds, when randomization is allowed. In this work, we consider spanner constructions in the congested clique model, and show: (1) A randomized construction of a $(2k-1)$-spanner with $\widetilde{O}(n^{1+1/k})$ edges in $O(\log k)$ rounds. The previous best algorithm runs in $O(k)$ rounds. (2) A deterministic construction of a $(2k-1)$-spanner with $\widetilde{O}(n^{1+1/k})$ edges in $O(\log k +(\log\log n)^3)$ rounds. The previous best algorithm runs in $O(k\log n)$ rounds. This improvement is achieved by a new derandomization theorem for hitting sets which might be of independent interest. (3) A deterministic construction of a $O(k)$-spanner with $O(k \cdot n^{1+1/k})$ edges in $O(\log k)$ rounds.

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k = 2 and there are n parties, there are schemes for sharing an ℓ-bit secret in which the share size of each party is roughly max{ℓ, logn} bits, and this is tight even for secrets of 1 b. In these schemes, the number of parties n must be given in advance to the dealer. In this paper, we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the tthparty arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure and 1-bit secrets where the share size of party t is (k-1)·logt+poly(k)·o(logt). Fork = 2 we observe an equivalence to prefix codes and present matching upper and lower bounds of the form log t + log log t + log log log t + O(1). Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2t-1.

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 while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision resistant hash function exist (which follows from the hardness of problems such as factoring, discrete-log and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is the succinct black-box, where there is a known upper bound on the size of the black-box (but no limit on the computation time). In this case we show that for all TFNP problems there is an upper bound on the number of queries proportional to the description size of the box times the solution size. On the other hand, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property which is hard to test even when one is given the program for computing the graph. The hard property is whether the graph is a two-source extractor.

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 of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of one-way functions, or even public-key cryptography. The only known hardness results are based on less general assumptions such as the existence of collision-resistant hash functions, one-way permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption). Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP? In this work, we answer this question and show that hard-on-average TFNP problems can be based on the weak assumption that there exists a hard-on-average language in NP. In particular, this includes the assumption of the existence of one-way functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs.

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 problem is defined by a continuous function, which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class CLS (Daskalakis and Papadimitriou SODA’11) which is contained in the intersection of PLS and PPAD, two important subclasses of TFNP (the class of NP search problems with a guaranteed solution). In this work, we show the first hardness results for CLS (the smallest non-trivial class among the currently defined subclasses of TFNP). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions. Our results demonstrate a strong conceptual barrier precluding design of efficient algorithms for solving local search problems even over continuous domains. As our main technical contribution we introduce a new total search problem which we call End-OF-Metered-Line. The special structure of End-OF-Metered-Line enables us to: (1) show that it is contained in CLS, and (2) prove hardness for it both in the black-box and the white-box setting.

A program obfuscator takes a program and outputs a "scrambled" version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013). This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters, STOC 2014). Most of them explicitly rely on additional hardness assumptions, such as one-way functions. Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if P ≠ NP, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if P ≠ NP and program obfuscation is possible, then one-way functions exist. Our main result is that if NP ⊈; io-BPP and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for NP. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average NP problems. To get some of our results we need obfuscators for simple programs such as 3CNF formulas