This paper studies the isomorphism problem for Boolean formulas and places it precisely in the polynomial hierarchy. Two of its results are new. The first sharpens the relationship between Boolean and graph isomorphism. Chang's reduction shows only that the unrestricted Boolean isomorphism problem is GI-hard, in one direction; restricting both ... more >>>

Two-server Private Information Retrieval achieves arbitrarily small polynomial communication, but relies on a strong non-collusion assumption that
is difficult to justify in practice.

We introduce a new variant of two-server PIR in which one server acts as a standard *compute* server, while the other is a restricted *retrieval-only* server. The ... more >>>

We continue the study of half-duplex communication complexity, a model introduced in [HIMS18] and further studied in [DISSU21], in which each player can either send a bit or listen in each round, similarly to communication over a walkie-talkie.
We prove improved upper bounds for the Inner Product function in the ... more >>>