We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.
Speaker: Ilan Komargodski
Affiliation: Cornell Tech
Title: White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing
Abstract: 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? This problem is in TFNP, the class of search problems with guaranteed solutions. 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.
1) What if one is given a program or circuit (“white-box”) for computing the existence of an edge. Does the search problem remain hard?
2) Can we generically translate all TFNP black-box hardness into white-box hardness?
3) Does the problem remain hard if the black-box instance is small?
We will answer all of these questions and discuss related questions in the setting of property testing.
Joint work with Moni Naor and Eylon Yogev.
Speaker: Ran Ben Basat
Title: Classic Network Measurement meets Virtual Switching
Abstract: In modern cloud infrastructures, each physical server often runs multiple virtual machines and employs a software Virtual Switch (VS) to handle their traffic. In addition to switching, the VS performs network measurements, such as identifying the most frequent flows, which are essential for networking applications such as load balancing and intrusion detection.
Unlike traditional streaming algorithms, which minimize the space requirements, the bottleneck in virtual switching measurement is the CPU utilization. In this talk, I will present new hardware-oriented algorithms and acceleration methods that optimize the update time for software, at the cost of a slight memory overhead.
Bio: Ran is a Ph.D. candidate at the Technion, Israel. He does research in streaming algorithms for networking applications, focusing on efficient processing and query speeds.
Speaker: Samson Zhou
Affiliation: Purdue University
Speaker: Venkata Gandikota
Affiliation: Johns Hopkins University
Title: NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem
Abstract: Establishing the complexity of Bounded Distance Decoding for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius).
We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length N and dimension K = O(N), we show that it is NP-hard to decode more than N-K-O(log N / log log N) errors.
These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called Moments Subset Sum, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.
This is a joint work with Badih Ghazi (MIT) and Elena Grigorescu (Purdue).