TCS+ talk: Wednesday, October 9 — Renato Ferreira Pinto Jr, U Waterloo
The next TCS+ talk will take place this coming Wednesday, October 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Renato Ferreira Pinto Jr from U Waterloo will speak about “”Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach“” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: This work explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions
on the solid unit cube, where the goal is to test with respect to the
distance. Our goals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting.
Our main results are 1) an
monotonicity tester for
-Lipschitz functions with query complexity
and, behind this result, 2) the directed Poincaré inequality
, where the “”directed gradient”” operator
measures the local violations of monotonicity of
.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function
over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.
. In this talk we will briefly review some applications of PFR in theoretical computer science, and go through the beautiful proof by Gowers, Green, Manners and Tao. Finally we will see some technical ideas in my recent work which can further improve their bound when 
.
on a graph with 
vertices and 
edges. For the case of very dense graphs, a different algorithm based on fast matrix multiplication was subsequently developed, with running time of 
. This remained the state of the art until recently, when a new method for solving maximum flow and related problems was introduced, that utilizes continuous optimization techniques, such as interior-point methods for solving linear programs. Following this, a sequence of remarkable new results that rely on this method have led to faster algorithms, culminating in a recent spectacular breakthrough, that gives an almost-linear time algorithm for maximum bipartite matching, and more generally, for min cost flow.
-approximate maximum flow problem in capacitated, undirected graphs with 
depth and 
work in the PRAM model. Although near-linear time sequential algorithms for this problem have been known for almost a decade, no parallel algorithms that simultaneously achieved polylogarithmic depth and near-linear work were known. At the heart of our result is a polylogarithmic depth, near-linear work recursive algorithm for computing congestion approximators. Our algorithm involves a recursive step to obtain a low-quality congestion approximator followed by a “boosting” step to improve its quality which prevents a multiplicative blow-up in error. Similar to Peng [SODA’16], our boosting step builds upon the hierarchical decomposition scheme of R\”acke, Shah, and T\”aubig [SODA’14]. A direct implementation of this approach, however, leads only to an algorithm with 
depth and 
work. To get around this, we introduce a new hierarchical decomposition scheme, in which we only need to solve maximum flows on subgraphs obtained by contracting vertices, as opposed to vertex-induced subgraphs used in R\”acke, Shah, and T\”aubig [SODA’14]. In particular, we are able to directly extract congestion approximators for the subgraphs from a congestion approximator for the entire graph, thereby avoiding additional recursion on those subgraphs. Along the way, we also develop a parallel flow-decomposition algorithm that is crucial to achieving polylogarithmic depth and may be of independent interest.
time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are 
[BLNPSSSW FOCS’20] and 
[AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01].
bound from over three decades ago [Gabow and Tarjan SICOMP’89].
TCS+ 