הכנס הארצי למדעי המחשב והמידע

Consider a revenue-maximizing seller who receives a signal about two bidders' joint values. The signal consists of exactly one bit of information. We explore what kind of information is most valuable to the seller.

We study three classes of signals, each capturing a distinct dimension of bidders' values: their overall level (demand), their relative strength (ranking), and their dispersion while preserving bidder anonymity (competitiveness). We characterize the optimal signal and corresponding auction mechanism within each class, and find that competitiveness signals are particularly effective.

We show that under certain regularity conditions, the optimal competitiveness signal yields at least as much revenue as any ranking signal or demand signal. Moreover, for signals that induce a monotone allocation, the optimal competitiveness signal yields at least as much revenue as any other binary signal.

Joint work with Itai Ashlagi, Jacob D. Leshno, Sigal Oren.

This talk will survey recent progress in distributed subgraph finding. We’ll then zoom out to examine some curious complexity gaps and the barriers faced by current techniques, both in subgraph finding and in other distributed graph problems. Join us on the quest for new techniques.

We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task T(x) (as opposed to artificial random hashing), in a permissionless setting where the miner itself chooses the input x. The challenge in designing such a Proof-of-Useful-Work (PoUW) protocol, is using the native computation of T(x) to produce a PoW certificate with prescribed hardness and with negligible computational overhead over the worst-case complexity of T(⋅) — This ensures malicious miners cannot “game the system” by fooling the verifier to accept with higher probability compared to honest miners (while using similar computational resources). Indeed, obtaining a PoUW with O(1)-factor overhead is trivial for any task T, but also useless.

Our main result is a PoUW for the task of Matrix Multiplication MatMul(A,B) of arbitrary matrices with 1+o(1) multiplicative overhead compared to naive MatMul. We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover.

We will discuss two hardness conjectures, based on batch random linear equations, and on SETH. This leads to a new notion of succinct random self-reducibility of functions which may be of independent interest.

A Bloom filter is a probabilistic data structure that provides a compact representation of a set S drawn from a large universe U. The price for this efficiency is the possibility of false positives: membership queries for elements in S are always answered correctly, while an element outside S may be reported as being in the set with small probability.

The standard analysis of Bloom filters assumes that queries are independent of the filter's internal randomness. In contrast, Naor and Yogev (CRYPTO 2015) initiated the study of Bloom filters in adversarial settings, where an adversary can choose queries adaptively based on previous answers.

A fundamental question in this setting is how to define and achieve robustness against an adaptive adversary. In this talk, we will revisit this question, explore several possible notions of success for an adaptive adversary, and present constructions that achieve these notions. Along the way, we will see that the choice of definition has a significant impact on what guarantees are possible.

Based on joint work with Eylon Yogev, Noa Oved, and Chen Lotan.