More Like this

1. Supermartingale shadow couplings: The decreasing case

   https://doi.org/10.3150/23-BEJ1592  

   Bayraktar, Erhan; Deng, Shuoqing; Norgilas, Dominykas (February 2024, Bernoulli)

   For two measures that are in convex-decreasing order, Nutz and Stebegg (Canonical supermartingale couplings, Ann. Probab. 46(6) 3351–3398, 2018) studied the optimal transport problem with supermartingale constraints and introduced two canonical couplings, namely the increasing and decreasing transport plans, that are optimal for a large class of cost functions. In the present paper we provide an explicit construction of the decreasing coupling by establishing a Brenier-type result: (a generalised version of) this coupling concentrates on the graphs of two functions. Our construction is based on the concept of the supermartingale shadow measure and requires a suitable extension of the results by Juillet (Stability of the shadow projection and the left-curtain coupling, Ann. Inst. H. Poincaré Probab. Statist. 52(4) 1823–1843, November 2016) and Beiglböck and Juillet (Shadow couplings, Trans. Amer. Math. Soc. 374 4973–5002, 2021) established in the martingale setting. In particular, we prove the stability of the supermartingale shadow measure with respect to initial and target measures introduce an infinite family of lifted supermartingale couplings that arise via shadow measure, and show how to explicitly determine the martingale points of each such coupling. 

   more » « less
2. General Strong Polarization

   https://doi.org/10.1145/3491390  

   Błasiok, Jarosław; Guruswami, Venkatesan; Nakkiran, Preetum; Rudra, Atri; Sudan, Madhu (April 2022, Journal of the ACM)

   Arıkan’s exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M , a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0, 1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arıkan showed appropriate polarization of the martingale associated with the matrix ( G 2 = ( 1 1 0 1) to get capacity achieving codes. His analysis was later extended to all matrices M that satisfy an obvious necessary condition for polarization. While Arıkan’s theorem does not guarantee that the codes achieve capacity at small blocklengths (specifically in length, which is a polynomial in ( 1ε ) where (ε) is the difference between the capacity of a channel and the rate of the code), it turns out that a “strong” analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with ( G 2 ) such a strong polarization was shown in two independent works (Guruswami and Xia (IEEE IT’15) and Hassani et al. (IEEE IT’14)), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are (in our view) also much simpler and modular. Key to our proof is a notion of local polarization that only depends on the evolution of the martingale in a single time step. We show that local polarization always implies strong polarization. We then apply relatively simple reasoning about conditional entropies to prove local polarization in very general settings. Specifically, our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels. We show how to use our analyses to achieve exponentially small error probabilities at lengths inverse polynomial in the gap to capacity. Indeed we show that we can essentially match any error probability while maintaining lengths that are only inverse polynomial in the gap to capacity. 

   more » « less
3. Dearomative ring expansion of thiophenes by bicyclobutane insertion

   https://doi.org/10.1126/science.adh9737  

   Wang, Huamin; Shao, Huiling; Das, Ankita; Dutta, Subhabrata; Chan, Hok Tsun; Daniliuc, Constantin; Houk, K. N.; Glorius, Frank (July 2023, Science)

   Skeletal ring enlargement is gaining renewed interest in synthetic chemistry and has recently focused on insertion of one or two atoms. Strategies for heterocyclic expansion through small-ring insertion remain elusive, although they would lead to the efficient formation of bicyclic products. Here, we report a photoinduced dearomative ring enlargement of thiophenes by insertion of bicyclo[1.1.0]butanes to produce eight-membered bicyclic rings under mild conditions. The synthetic value, broad functional-group compatibility, and excellent chemo- and regioselectivity were demonstrated by scope evaluation and product derivatization. Experimental and computational studies point toward a photoredox-induced radical pathway. 

   more » « less
4. Polar Codes with Exponentially Small Error at Finite Block Length

   https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.34  

   Blasiok, Jaroslaw; Guruswami, Venkatesan; Sudan, Mahdu (January 2018, Leibniz international proceedings in informatics)

   We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability exp(-N^{Omega(1)}) for codes of length N). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the time-local behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the "Arikan martingale", exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes that achieve failure probability exp(-N^{beta}) for any beta < 1 while converging to capacity at block length polynomial in the gap to capacity. Finally we also show that the "local" approach can be combined with any analysis of failure probability of an arbitrary polar code to get essentially the same failure probability while achieving block length polynomial in the gap to capacity. 

   more » « less
5. General strong polarization

   https://doi.org/10.1145/3188745.3188816  

   Błasiok, Jarosław; Guruswami, Venkatesan; Nakkiran, Preetum; Rudra, Atri; Sudan, Madhu (June 2018, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,)

   Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2=(1011) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization. While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with G2 such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are (in our view) also much simpler and modular. Key to our proof is a notion of local polarization that only depends on the evolution of the martingale in a single time step. Our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels. 

   more » « less