## Organizer(s) | Swastik Kopparty, Shubhangi Saraf | ## Archive | |

## Website | http://www.math.rutgers.edu/~sk1233/theory-seminar/S17/ |

## Upcoming Talks

## Wednesday, March 1st |

## Avishay Tal , |

## "TBA" |

Time: 11:00 AM |

Location: CoRE 301 |

## Past Talks

## Wednesday, February 15th |

## Muthuramakrishnan Venkitasubramaniam , |

## "Equivocating Yao: Constant-Rounds Adaptively Secure Multiparty Computation in the Plain Model" |

Time: 11:00 AM |

Location: CoRE 301 |

Abstract:
Yao’s circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?
We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-rounds multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UC-security) and applications to leakage resilience. |

## Wednesday, February 8th |

## Yash Kanoria, |

## "Communication requirements and Informative signaling in matching markets" |

Time: 11:00 AM |

Location: CoRE 301 |

Abstract: We study the amount of communication needed to fi nd a stable matching in a two-sided matching market with private preferences when agents have some knowledge of the preference distribution. In a two-sided market with workers and fi rms, when the preferences of workers are arbitrary and private and the preferences of firms follow an additively separable latent utility model with commonly known and heterogeneous parameters, we describe an algorithm that fi nds a stable matching with high probability and requires at most O*(sqrt{n}) bits of communication per agent. (We also show that this is the best possible under this setting.) Our algorithm is a modification of worker-proposing deferred acceptance that skips wasteful applications. Firms help workers better target applications by signaling workers that they privately like and broadcasting to the market a qualifi cation requirement to discourage those with no realistic chances from applying. Our results yield insights on how matching markets can be better organized to reduce congestion. Broadly, agents should reach out to their favorites among "gettable" partners, while waiting for their dream matches to reach out to them.
Joint work with Itai Ashlagi, Mark Braverman and Peng Shi. |

## Wednesday, February 1st |

## Clement Cannone, |

## "Alice and Bob Show Distribution Testing Lower Bounds (They don’t talk to each other anymore.)" |

Time: 11:00 AM |

Location: CoRE 301 |

Abstract: We present a new methodology for proving distribution testing lower
bounds, establishing a connection between distribution testing and the
simultaneous message passing (SMP) communication model. Extending the
framework of Blais, Brody, and Matulef [BBM12], we show a simple way to
reduce (private-coin) SMP problems to distribution testing problems.
This method allows us to prove several new distribution testing lower
bounds, as well as to provide simple proofs of known lower bounds.
Our main result is concerned with testing identity to a specific distribution p, given as a parameter. In a recent and influential work, Valiant and Valiant [VV14] showed that the sample complexity of the aforementioned problem is closely related to the 2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre's K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction. Joint work with Eric Blais (University of Waterloo) and Tom Gur (Weizmann Institute) |

## Wednesday, January 25th |

## Matt Weinberg, |

## "Simultaneous Communication Complexity of Two-Player Combinatorial Auctions " |

Time: 11:00 AM |

Location: CoRE 301 |

Abstract: We consider simultaneous protocols for the following communication problem: Alice and Bob each have some list of subsets of [m], A_1,...,A_a, and B_1,...,B_b, and wish to either:
(Allocation Problem): partition [m] into A sqcup B in order to maximize max_i {A cap A_i} + max_j {B cap B_j}. (Decision Problem): decide whether there exists an i, j, such that A_i cup B_ j geq C. For interactive protocols, a (tight) 3/4-approximation is known in poly(m) communication for both problems. We show the following: - A randomized, simultaneous protocol with O(m) communication that achieves a (tight) 3/4-approximation for the allocation problem. - No randomized, simultaneous protocol with subexponential (in m) communication guarantees better than a 3/4-1/108 approximation for the decision problem. I'll further discuss the implications of these results for truthful combinatorial auctions due to a recent result of Dobzinski [FOCS 16]. Joint work with Mark Braverman and Jieming Mao. |

## Wednesday, January 18th - CANCELLED |

## Muthuramakrishnan Venkitasubramaniam, |

## "Equivocating Yao: Constant-Rounds Adaptively Secure Multiparty Computation in the Plain Model " |

Time: 11:00 AM |

Location: CoRE 301 |

Abstract: Yao’s circuit garbling scheme is one of the basic building blocks of crytographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?
We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-rounds multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UC-security) and applications to leakage resilience. |