More Like this

1. Reductions in PPP

   https://doi.org/10.1016/j.ipl.2018.12.009  

   Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (May 2019, Information Processing Letters)
2. Algebraic Reductions of Knowledge

   https://doi.org/10.1007/978-3-031-38551-3_21  

   Kothapalli, Abhiram; Parno, Bryan (January 2023, Advances in Cryptology – CRYPTO)
3. Maximal Simplification of Polyhedral Reductions

   https://doi.org/10.1145/3704839  

   Narmour, Louis; Yuki, Tomofumi; Rajopadhye, Sanjay (January 2025, Proceedings of the ACM on Programming Languages)

   Reductions combine collections of input values with an associative and often commutative operator to produce collections of results. When the same input value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. Simplification often produces a program with lower asymptotic complexity. Typical compiler optimizations yield, at best, a constant fold speedup, but a complexity improvement from, say, cubic to quadratic complexity yields unbounded speedup for sufficiently large problems. It is well known that reductions in polyhedral programs may be simplified automatically, but previous methods cannot exploit all available reuse. This paper resolves this long-standing open problem, thereby attaining minimal asymptotic complexity in the simplified program. We propose extensions to prior work on simplification to support any independent commutative reduction. At the heart of our approach is piece-wise simplification, the notion that we can split an arbitrary reduction into pieces and then independently simplify each piece. However, the difficulty of using such piece-wise transformations is that they typically involve an infinite number of choices. We give constructive proofs to deal with this and select a finite number of pieces for simplification. 

   more » « less
4. Simpler reductions from Exact Triangle.

   https://doi.org/10.1137/1.9781611977936.4  

   Chan, Timothy M.; Xu, Yinzhan (January 2024, Proc. 7th SIAM Sympos. Simplicity of Algorithms (SOSA))
5. Abelian varieties with isogenous reductions

   https://doi.org/https://doi.org/10.5802/crmath.129  

   Khare, Chandreshekhar; Larsen, Michael: (October 2020, Comptes rendus)

   null (Ed.)

   Let $$A_1$$ and $$A_2$$ be abelian varieties over a number field $$K$$. We prove that if there exists a non-trivial morphism of abelian varieties between reductions of $$A_1$$ and $$A_2$$ at a sufficiently high percentage of primes, then there exists a non-trivial morphism $$A_1\to A_2$$ over $$\bar K$$. Along the way, we give an upper bound for the number of components of a reductive subgroup of $$GL_n$$ whose intersection with the union of $$Q$$-rational conjugacy classes of $$GL_n$$ is Zariski-dense. This can be regarded as a generalization of the Minkowski-Schur theorem on faithful representations of finite groups with rational characters. 

   more » « less