Faculty Recruiting Support CICS

Theory Seminar

18 Oct
Tuesday, 10/18/2022 4:00pm to 5:00pm
Computer Science Building, Room 140
Theory Seminar
This Theory Seminar will feature three back-to-back student talks featuring Jacob Gray (UMass), Jacob Goldman (UMass), Joseph Black (UMass)    

Speaker: Jacob Gray

Title: Adapting Truth-Table Reducibility to Zero-Knowledge with Logspace 

Abstract: The zero-knowledge proof model has been around for many years, but recently, NISZK_L, a new subclass of the non-interactive statistical variant, has gained interest due to its relation to the minimum circuit size problem, an important potential NP-intermediate problem. As strong closure properties for NISZK_L appear elusive, one of the routes we took to get better insight into this class was to ensure that an analogous class, SZK_L, maintained SZK's closure under a boolean-formula truth-table reduction.

In this talk, I plan to give a general, intuitive explanation of what zero-knowledge proofs are, what statistical zero knowledge looks like, and an outline of the adaptation for this closure property to SZK_L. Although NISZK_L is a large motivator for this result, I will only introduce and talk about SZK_L.

This is joint work done with Eric Allender, Harsha Tirumala, Sachi Mutreja, and Pengxiang Wang as part of the 2022 DIMACS REU at Rutgers.

Speaker: Jacob Goldman

Title: Almost Tight Approximation Algorithms for Explainable Clustering

Abstract: The increasing desire for transparency in artificial intelligence motivates the study of algorithms that are both accurate and interpretable by humans. In this talk, I'll discuss the work of a Google Research team studying k-medians and k-means clustering under a recent framework of explainable clustering first suggested by Dasgupta et al. Under this framework, the space of points to be clustered is decomposed using a decision tree where each node separates two clusters by simple comparison in one of the dimensions of the space. I'll present their O(log k log log k)-approximation algorithm for explainable k-medians and their O(k log k)-approximation algorithm for explainable k-means, both of which are improvements over the respective best algorithms for each problem.

Speaker: Joseph Black

Title: PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing

Abstract: This paper presents interactive image editing tools using a new randomized algorithm for quickly finding approximate nearest-neighbor matches between image patches. Previous research in graphics and vision has leveraged such nearest-neighbor searches to provide a variety of high-level digital image editing tools. However, the cost of computing a field of such matches for an entire image has eluded previous efforts to provide interactive performance. Our algorithm offers substantial performance improvements over the previous state of the art (20-100x), enabling its use in interactive editing tools. The key insights driving the algorithm are that some good patch matches can be found via random sampling, and that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. We offer theoretical analysis of the convergence properties of the algorithm, as well as empirical and practical evidence for its high quality and performance. This one simple algorithm forms the basis for a variety of tools - image retargeting, completion and reshuffling - that can be used together in the context of a high-level image editing application. Finally, we propose additional intuitive constraints on the synthesis process that offer the user a level of control unavailable in previous methods.

The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.