Re: TCS+ talk *this week*: Wednesday, October 9, Renato Ferreira Pinto Jr, U Waterloo
9 views
Skip to first unread message
Clement Canonne
Oct 8, 2024, 7:41:05 PM10/8/24
to tcsplus_...@googlegroups.com
Hi all,
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow, starting at 12:50pm ET:
https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09 (you will need a to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ Admin <tcsplu...@googlegroups.com>
Sent: Monday, 7 October 2024 11:59 PM
To: tcsplu...@googlegroups.com
Subject: TCS+ talk *this week*: Wednesday, October 9, Renato Ferreira Pinto Jr, U Waterloo
Hello everyone,
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, October 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://url.au.m.mimecastprotect.com/s/YUJ2CMwGxOtxwByN6iwfwF8zExu?domain=sites.google.com before the talk starts.
If you’d like to join the Zoom talk, please sign up using the form at https://url.au.m.mimecastprotect.com/s/5RS0CNLJyQUVOkq4MU4hXFyWbrr?domain=sites.google.com. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: https://url.au.m.mimecastprotect.com/s/_Q5UCOMKzVT571LW2ikiYFG9au3?domain=youtube.com.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Renato Ferreira Pinto Jr (U Waterloo)
Title: Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Abstract: This work explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ 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 $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed Poincaré inequality $\mathsf{dist}^{\mathsf{mono}}_2(f)^2 \le C \mathbb{E}[|\nabla^- f|^2]$, where the ""directed gradient"" operator $\nabla^-$ measures the local violations of monotonicity of $f$.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ 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.
--
You received this message because you are subscribed to the Google Groups "TCS+ Admin" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus-admi...@googlegroups.com.
To view this discussion on the web visit https://url.au.m.mimecastprotect.com/s/AJyjCP7LAXfvjz1p5FjsRFxA-d8?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/D68bCQnMBZfB2v10NSrtvFGiU1M?domain=groups.google.com.
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow, starting at 12:50pm ET:
https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09 (you will need a to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ Admin <tcsplu...@googlegroups.com>
Sent: Monday, 7 October 2024 11:59 PM
To: tcsplu...@googlegroups.com
Subject: TCS+ talk *this week*: Wednesday, October 9, Renato Ferreira Pinto Jr, U Waterloo
Hello everyone,
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, October 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://url.au.m.mimecastprotect.com/s/YUJ2CMwGxOtxwByN6iwfwF8zExu?domain=sites.google.com before the talk starts.
If you’d like to join the Zoom talk, please sign up using the form at https://url.au.m.mimecastprotect.com/s/5RS0CNLJyQUVOkq4MU4hXFyWbrr?domain=sites.google.com. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: https://url.au.m.mimecastprotect.com/s/_Q5UCOMKzVT571LW2ikiYFG9au3?domain=youtube.com.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Renato Ferreira Pinto Jr (U Waterloo)
Title: Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Abstract: This work explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ 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 $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed Poincaré inequality $\mathsf{dist}^{\mathsf{mono}}_2(f)^2 \le C \mathbb{E}[|\nabla^- f|^2]$, where the ""directed gradient"" operator $\nabla^-$ measures the local violations of monotonicity of $f$.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ 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.
--
You received this message because you are subscribed to the Google Groups "TCS+ Admin" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus-admi...@googlegroups.com.
To view this discussion on the web visit https://url.au.m.mimecastprotect.com/s/AJyjCP7LAXfvjz1p5FjsRFxA-d8?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/D68bCQnMBZfB2v10NSrtvFGiU1M?domain=groups.google.com.
Reply all
Reply to author
Forward
0 new messages