Latest articles https://theoretics.episciences.org/img/episciences_sign_50x50.png https://theoretics.episciences.org Tue, 07 Apr 2026 01:34:24 +0000 episciences.org https://theoretics.episciences.org TheoretiCS TheoretiCS Thu, 26 Feb 2026 08:28:07 +0000 https://doi.org/10.46298/theoretics.26.6 https://doi.org/10.46298/theoretics.26.6 Lohrey, Markus Schmid, Markus L. Lohrey, Markus Schmid, Markus L. 0 Tue, 24 Feb 2026 12:22:15 +0000 https://doi.org/10.46298/theoretics.26.5 https://doi.org/10.46298/theoretics.26.5 Casares, Antonio Ohlmann, Pierre Casares, Antonio Ohlmann, Pierre 0 Mon, 23 Feb 2026 10:14:38 +0000 https://doi.org/10.46298/theoretics.26.4 https://doi.org/10.46298/theoretics.26.4 Grohe, Martin Neuen, Daniel Grohe, Martin Neuen, Daniel 0 Thu, 29 Jan 2026 08:43:37 +0000 https://doi.org/10.46298/theoretics.26.3 https://doi.org/10.46298/theoretics.26.3 Assadi, Sepehr Yazdanyar, Helia Assadi, Sepehr Yazdanyar, Helia 0 Tue, 13 Jan 2026 08:34:20 +0000 https://doi.org/10.46298/theoretics.26.2 https://doi.org/10.46298/theoretics.26.2 Abrahamsen, Mikkel Blikstad, Joakim Nusser, André Zhang, Hanwen Abrahamsen, Mikkel Blikstad, Joakim Nusser, André Zhang, Hanwen 0 Tue, 13 Jan 2026 08:32:28 +0000 https://doi.org/10.46298/theoretics.26.1 https://doi.org/10.46298/theoretics.26.1 Bencs, Ferenc Berrekkal, Khallil Regts, Guus Bencs, Ferenc Berrekkal, Khallil Regts, Guus 0 Thu, 18 Dec 2025 09:29:03 +0000 https://doi.org/10.46298/theoretics.25.29 https://doi.org/10.46298/theoretics.25.29 Bhandari, Siddharth Harsha, Prahladh Kumar, Mrinal Shankar, Ashutosh Bhandari, Siddharth Harsha, Prahladh Kumar, Mrinal Shankar, Ashutosh 0 Tue, 02 Dec 2025 09:29:03 +0000 https://doi.org/10.46298/theoretics.25.28 https://doi.org/10.46298/theoretics.25.28 Bacik, Piotr Bacik, Piotr 0 Mon, 01 Dec 2025 09:01:48 +0000 https://doi.org/10.46298/theoretics.25.27 https://doi.org/10.46298/theoretics.25.27 Håstad, Johan Håstad, Johan 0 Wed, 26 Nov 2025 14:49:16 +0000 https://doi.org/10.46298/theoretics.25.26 https://doi.org/10.46298/theoretics.25.26 Arora, Atul Singh Roland, Jérémie Vlachou, Chrysoula Weis, Stephan Arora, Atul Singh Roland, Jérémie Vlachou, Chrysoula Weis, Stephan 0 Thu, 16 Oct 2025 22:00:00 +0000 https://doi.org/10.46298/theoretics.25.25 https://doi.org/10.46298/theoretics.25.25 Jungeblut, Paul Merker, Laura Ueckerdt, Torsten Jungeblut, Paul Merker, Laura Ueckerdt, Torsten 0 Thu, 16 Oct 2025 07:31:26 +0000 https://doi.org/10.46298/theoretics.25.24 https://doi.org/10.46298/theoretics.25.24 Kasliwal, Shashwat Polak, Adam Sharma, Pratyush Kasliwal, Shashwat Polak, Adam Sharma, Pratyush 0 Wed, 15 Oct 2025 08:05:48 +0000 https://doi.org/10.46298/theoretics.25.23 https://doi.org/10.46298/theoretics.25.23 Huiberts, Sophie Lee, Yin Tat Zhang, Xinzhi Huiberts, Sophie Lee, Yin Tat Zhang, Xinzhi 0 Fri, 10 Oct 2025 07:48:53 +0000 https://doi.org/10.46298/theoretics.25.22 https://doi.org/10.46298/theoretics.25.22 Filtser, Arnold Friedrich, Tobias Issac, Davis Kumar, Nikhil Le, Hung Mallek, Nadym Zeif, Ziena Filtser, Arnold Friedrich, Tobias Issac, Davis Kumar, Nikhil Le, Hung Mallek, Nadym Zeif, Ziena 0 Thu, 02 Oct 2025 08:18:57 +0000 https://doi.org/10.46298/theoretics.25.21 https://doi.org/10.46298/theoretics.25.21 Eiben, Eduard Koana, Tomohiro Wahlström, Magnus Eiben, Eduard Koana, Tomohiro Wahlström, Magnus 0 Wed, 01 Oct 2025 07:16:46 +0000 https://doi.org/10.46298/theoretics.25.20 https://doi.org/10.46298/theoretics.25.20 Harms, Nathaniel Wild, Sebastian Zamaraev, Viktor Harms, Nathaniel Wild, Sebastian Zamaraev, Viktor 0 Fri, 22 Aug 2025 06:56:13 +0000 https://doi.org/10.46298/theoretics.25.19 https://doi.org/10.46298/theoretics.25.19 Collins, Nathaniel A. Grochow, Joshua A. Levet, Michael Weiß, Armin Collins, Nathaniel A. Grochow, Joshua A. Levet, Michael Weiß, Armin 0 Tue, 19 Aug 2025 07:14:07 +0000 https://doi.org/10.46298/theoretics.25.18 https://doi.org/10.46298/theoretics.25.18 Zhandry, Mark Zhandry, Mark 0 Thu, 14 Aug 2025 07:20:15 +0000 https://doi.org/10.46298/theoretics.25.17 https://doi.org/10.46298/theoretics.25.17 Feng, Yuda Li, Shi Feng, Yuda Li, Shi 0 Fri, 01 Aug 2025 13:02:57 +0000 https://doi.org/10.46298/theoretics.25.16 https://doi.org/10.46298/theoretics.25.16 Assadi, Sepehr Assadi, Sepehr 0 Fri, 18 Jul 2025 09:31:50 +0000 https://doi.org/10.46298/theoretics.25.15 https://doi.org/10.46298/theoretics.25.15 Cslovjecsek, Jana Koutecký, Martin Lassota, Alexandra Pilipczuk, Michał Polak, Adam Cslovjecsek, Jana Koutecký, Martin Lassota, Alexandra Pilipczuk, Michał Polak, Adam 0 Thu, 17 Jul 2025 06:59:02 +0000 https://doi.org/10.46298/theoretics.25.14 https://doi.org/10.46298/theoretics.25.14 Fischer, Nick Wennmann, Leo Fischer, Nick Wennmann, Leo 0 Mon, 16 Jun 2025 15:04:46 +0000 https://doi.org/10.46298/theoretics.25.13 https://doi.org/10.46298/theoretics.25.13 Bosch-Calvo, Miguel Grandoni, Fabrizio Ameli, Afrouz Jabal Bosch-Calvo, Miguel Grandoni, Fabrizio Ameli, Afrouz Jabal 0 Wed, 30 Apr 2025 10:04:41 +0000 https://doi.org/10.46298/theoretics.25.12 https://doi.org/10.46298/theoretics.25.12 Khamis, Mahmoud Abo Ngo, Hung Q. Suciu, Dan Khamis, Mahmoud Abo Ngo, Hung Q. Suciu, Dan 0 Tue, 08 Apr 2025 15:18:14 +0000 https://doi.org/10.46298/theoretics.25.11 https://doi.org/10.46298/theoretics.25.11 Chang, Yi-Jun Chang, Yi-Jun 0 Tue, 01 Apr 2025 15:22:37 +0000 https://doi.org/10.46298/theoretics.25.10 https://doi.org/10.46298/theoretics.25.10 Brázdil, Tomáš Chatterjee, Krishnendu Chmelik, Martin Forejt, Vojtěch Křetínský, Jan Kwiatkowska, Marta Meggendorfer, Tobias Parker, David Ujma, Mateusz Brázdil, Tomáš Chatterjee, Krishnendu Chmelik, Martin Forejt, Vojtěch Křetínský, Jan Kwiatkowska, Marta Meggendorfer, Tobias Parker, David Ujma, Mateusz 0 Tue, 25 Mar 2025 09:56:26 +0000 https://doi.org/10.46298/theoretics.25.9 https://doi.org/10.46298/theoretics.25.9 de Rezende, Susanna F. Nordström, Jakob Risse, Kilian Sokolov, Dmitry de Rezende, Susanna F. Nordström, Jakob Risse, Kilian Sokolov, Dmitry 0 \epsilon n$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space.]]> Thu, 06 Mar 2025 08:47:58 +0000 https://doi.org/10.46298/theoretics.25.8 https://doi.org/10.46298/theoretics.25.8 Ganardi, Moses Hucke, Danny Lohrey, Markus Mamouras, Konstantinos Starikovskaya, Tatiana Ganardi, Moses Hucke, Danny Lohrey, Markus Mamouras, Konstantinos Starikovskaya, Tatiana \epsilon n$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space.]]> 0 Tue, 04 Mar 2025 10:48:58 +0000 https://doi.org/10.46298/theoretics.25.7 https://doi.org/10.46298/theoretics.25.7 Jeffery, Stacey Zur, Sebastian Jeffery, Stacey Zur, Sebastian 0 Fri, 28 Feb 2025 10:41:29 +0000 https://doi.org/10.46298/theoretics.25.6 https://doi.org/10.46298/theoretics.25.6 Cambus, Mélanie Kuhn, Fabian Lindy, Etna Pai, Shreyas Uitto, Jara Cambus, Mélanie Kuhn, Fabian Lindy, Etna Pai, Shreyas Uitto, Jara 0 Wed, 22 Jan 2025 10:36:03 +0000 https://doi.org/10.46298/theoretics.25.5 https://doi.org/10.46298/theoretics.25.5 Avni, Guy Sadhukhan, Suman Avni, Guy Sadhukhan, Suman 0 Mon, 20 Jan 2025 09:54:14 +0000 https://doi.org/10.46298/theoretics.25.4 https://doi.org/10.46298/theoretics.25.4 Fleischmann, Henry Gavva, Surya Teja S, Karthik C. Fleischmann, Henry Gavva, Surya Teja S, Karthik C. 0 0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$. For the hard-core model, Weitz's algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when $\lambda = o(\Delta^{-2})$. Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant.]]> Mon, 13 Jan 2025 11:35:49 +0000 https://doi.org/10.46298/theoretics.25.3 https://doi.org/10.46298/theoretics.25.3 Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng 0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$. For the hard-core model, Weitz's algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when $\lambda = o(\Delta^{-2})$. Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant.]]> 0 Fri, 10 Jan 2025 10:36:42 +0000 https://doi.org/10.46298/theoretics.25.2 https://doi.org/10.46298/theoretics.25.2 Bodwin, Greg Bodwin, Greg 0 Wed, 08 Jan 2025 15:48:53 +0000 https://doi.org/10.46298/theoretics.25.1 https://doi.org/10.46298/theoretics.25.1 Filiot, Emmanuel Jecker, Ismaël Löding, Christof Muscholl, Anca Puppis, Gabriele Winter, Sarah Filiot, Emmanuel Jecker, Ismaël Löding, Christof Muscholl, Anca Puppis, Gabriele Winter, Sarah 0 Thu, 19 Dec 2024 08:18:38 +0000 https://doi.org/10.46298/theoretics.24.26 https://doi.org/10.46298/theoretics.24.26 Akmal, Shyan Akmal, Shyan 0 Wed, 04 Dec 2024 08:45:26 +0000 https://doi.org/10.46298/theoretics.24.25 https://doi.org/10.46298/theoretics.24.25 Grohe, Martin Grohe, Martin 0 Mon, 18 Nov 2024 13:34:54 +0000 https://doi.org/10.46298/theoretics.24.24 https://doi.org/10.46298/theoretics.24.24 Husić, Edin Loho, Georg Smith, Ben Végh, László A. Husić, Edin Loho, Georg Smith, Ben Végh, László A. 0 Tue, 05 Nov 2024 09:04:51 +0000 https://doi.org/10.46298/theoretics.24.23 https://doi.org/10.46298/theoretics.24.23 Cho, Kyungjin Oh, Eunjin Wang, Haitao Xue, Jie Cho, Kyungjin Oh, Eunjin Wang, Haitao Xue, Jie 0 Fri, 04 Oct 2024 08:29:14 +0000 https://doi.org/10.46298/theoretics.24.22 https://doi.org/10.46298/theoretics.24.22 Bringmann, Karl Grønlund, Allan Künnemann, Marvin Larsen, Kasper Green Bringmann, Karl Grønlund, Allan Künnemann, Marvin Larsen, Kasper Green 0 0$; the best bound until now is $\omega<2.37287$ [Le Gall'14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date: $$\omega < 2.37286.$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.]]> Wed, 04 Sep 2024 21:07:40 +0000 https://doi.org/10.46298/theoretics.24.21 https://doi.org/10.46298/theoretics.24.21 Alman, Josh Williams, Virginia Vassilevska Alman, Josh Williams, Virginia Vassilevska 0$; the best bound until now is $\omega<2.37287$ [Le Gall'14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date: $$\omega < 2.37286.$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.]]> 0 Mon, 02 Sep 2024 14:56:46 +0000 https://doi.org/10.46298/theoretics.24.20 https://doi.org/10.46298/theoretics.24.20 Roberson, David E. Seppelt, Tim Roberson, David E. Seppelt, Tim 0 Mon, 12 Aug 2024 06:49:06 +0000 https://doi.org/10.46298/theoretics.24.19 https://doi.org/10.46298/theoretics.24.19 Morelle, Laure Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. Morelle, Laure Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. 0 Tue, 30 Jul 2024 07:27:49 +0000 https://doi.org/10.46298/theoretics.24.18 https://doi.org/10.46298/theoretics.24.18 Dinur, Irit Filmus, Yuval Harsha, Prahladh Dinur, Irit Filmus, Yuval Harsha, Prahladh 0 Tue, 30 Jul 2024 07:25:44 +0000 https://doi.org/10.46298/theoretics.24.17 https://doi.org/10.46298/theoretics.24.17 Bohn, León Löding, Christof Bohn, León Löding, Christof 0 Fri, 12 Jul 2024 04:24:58 +0000 https://doi.org/10.46298/theoretics.24.16 https://doi.org/10.46298/theoretics.24.16 Chen, Zongchen Liu, Kuikui Vigoda, Eric Chen, Zongchen Liu, Kuikui Vigoda, Eric 0 0$, a randomized $f$-DSO with stretch $ 3 + \varepsilon$ that w.h.p. takes $\widetilde{O}(n^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+2}$ space and has an $O(n^\alpha/\varepsilon^2)$ query time. The time to build the oracle is $\widetilde{O}(mn^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k-1$ that w.h.p. takes $O(D^{f+o(1)} n^{1+1/k})$ space and has $\widetilde{O}(D^{o(1)})$ query time, with a preprocessing time of $O(D^{f+o(1)} mn^{1/k})$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1{+}\varepsilon$ and preprocessing time $O(n^{5+o(1)}/\varepsilon^f)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O(mn^{2+o(1)}/\varepsilon^f)$.]]> Wed, 05 Jun 2024 13:19:52 +0000 https://doi.org/10.46298/theoretics.24.15 https://doi.org/10.46298/theoretics.24.15 Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Krogmann, Simon Schirneck, Martin Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Krogmann, Simon Schirneck, Martin 0$, a randomized $f$-DSO with stretch $ 3 + \varepsilon$ that w.h.p. takes $\widetilde{O}(n^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+2}$ space and has an $O(n^\alpha/\varepsilon^2)$ query time. The time to build the oracle is $\widetilde{O}(mn^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k-1$ that w.h.p. takes $O(D^{f+o(1)} n^{1+1/k})$ space and has $\widetilde{O}(D^{o(1)})$ query time, with a preprocessing time of $O(D^{f+o(1)} mn^{1/k})$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1{+}\varepsilon$ and preprocessing time $O(n^{5+o(1)}/\varepsilon^f)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O(mn^{2+o(1)}/\varepsilon^f)$.]]> 0 Wed, 15 May 2024 08:36:31 +0000 https://doi.org/10.46298/theoretics.24.14 https://doi.org/10.46298/theoretics.24.14 Barto, Libor Brady, Zarathustra Bulatov, Andrei Kozik, Marcin Zhuk, Dmitriy Barto, Libor Brady, Zarathustra Bulatov, Andrei Kozik, Marcin Zhuk, Dmitriy 0 Mon, 06 May 2024 16:52:08 +0000 https://doi.org/10.46298/theoretics.24.13 https://doi.org/10.46298/theoretics.24.13 Bojańczyk, Mikołaj Fijalkow, Joanna Klin, Bartek Moerman, Joshua Bojańczyk, Mikołaj Fijalkow, Joanna Klin, Bartek Moerman, Joshua 0 Fri, 26 Apr 2024 07:42:59 +0000 https://doi.org/10.46298/theoretics.24.11 https://doi.org/10.46298/theoretics.24.11 Abrahamsen, Mikkel Miltzow, Tillmann Seiferth, Nadja Abrahamsen, Mikkel Miltzow, Tillmann Seiferth, Nadja 0 Wed, 24 Apr 2024 14:51:44 +0000 https://doi.org/10.46298/theoretics.24.12 https://doi.org/10.46298/theoretics.24.12 Casares, Antonio Colcombet, Thomas Fijalkow, Nathanaël Lehtinen, Karoliina Casares, Antonio Colcombet, Thomas Fijalkow, Nathanaël Lehtinen, Karoliina 0 , \wedge, \vee, \neg\}$, the goal is to check whether this sentence is true. Now the class ER is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP $\subseteq$ ER $\subseteq$ PSPACE. We restrict our attention on CCSPs with addition constraints ($x + y = z$) and some other mild technical conditions. Previously, it was shown that multiplication constraints ($x \cdot y = z$), squaring constraints ($x^2 = y$), or inversion constraints ($x\cdot y = 1$) are sufficient to establish ER-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical conditions) that have any one well-behaved curved equality constraint ($f(x,y) = 0$) are ER-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint ($f(x,y) \geq 0$ and $g(x,y) \geq 0$) imply ER-completeness on the class of such CCSPs.]]> Tue, 16 Apr 2024 08:17:28 +0000 https://doi.org/10.46298/theoretics.24.10 https://doi.org/10.46298/theoretics.24.10 Miltzow, Tillmann Schmiermann, Reinier F. Miltzow, Tillmann Schmiermann, Reinier F. , \wedge, \vee, \neg\}$, the goal is to check whether this sentence is true. Now the class ER is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP $\subseteq$ ER $\subseteq$ PSPACE. We restrict our attention on CCSPs with addition constraints ($x + y = z$) and some other mild technical conditions. Previously, it was shown that multiplication constraints ($x \cdot y = z$), squaring constraints ($x^2 = y$), or inversion constraints ($x\cdot y = 1$) are sufficient to establish ER-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical conditions) that have any one well-behaved curved equality constraint ($f(x,y) = 0$) are ER-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint ($f(x,y) \geq 0$ and $g(x,y) \geq 0$) imply ER-completeness on the class of such CCSPs.]]> 0 Mon, 08 Apr 2024 06:12:45 +0000 https://doi.org/10.46298/theoretics.24.9 https://doi.org/10.46298/theoretics.24.9 Piribauer, Jakob Baier, Christel Piribauer, Jakob Baier, Christel 0 Wed, 03 Apr 2024 07:36:36 +0000 https://doi.org/10.46298/theoretics.24.8 https://doi.org/10.46298/theoretics.24.8 Dhar, Manik Dvir, Zeev Dhar, Manik Dvir, Zeev 0 Mon, 18 Mar 2024 08:40:29 +0000 https://doi.org/10.46298/theoretics.24.7 https://doi.org/10.46298/theoretics.24.7 Bădescu, Costin O'Donnell, Ryan Bădescu, Costin O'Donnell, Ryan 0 0$ satisfying \begin{equation*} \forall x\in T\ \forall q\in X,\ C d_X(x, q) \le d_Y(f(x), f(q)) \le C \rho d_X(x, q) . \end{equation*} When $X,Y$ are both Euclidean metrics with $Y$ being $m$-dimensional, recently (Narayanan, Nelson 2019), following work of (Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion $1+\epsilon$ is achievable via such a terminal embedding with $m = O(\epsilon^{-2}\log n)$ for $n := |T|$. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within $T$ and not to $T$ from the rest of space. The downside of prior work is that evaluating their embedding on some $q\in \mathbb{R}^d$ required solving a semidefinite program with $\Theta(n)$ constraints in~$m$ variables and thus required some superlinear $\mathrm{poly}(n)$ runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process $T$ to obtain an almost linear-space data structure that supports computing the terminal embedding image of any $q\in\mathbb{R}^d$ in sublinear time $O^* (n^{1-\Theta(\epsilon^2)} + d)$. To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.]]> Thu, 14 Mar 2024 10:09:55 +0000 https://doi.org/10.46298/theoretics.24.6 https://doi.org/10.46298/theoretics.24.6 Cherapanamjeri, Yeshwanth Nelson, Jelani Cherapanamjeri, Yeshwanth Nelson, Jelani 0$ satisfying \begin{equation*} \forall x\in T\ \forall q\in X,\ C d_X(x, q) \le d_Y(f(x), f(q)) \le C \rho d_X(x, q) . \end{equation*} When $X,Y$ are both Euclidean metrics with $Y$ being $m$-dimensional, recently (Narayanan, Nelson 2019), following work of (Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion $1+\epsilon$ is achievable via such a terminal embedding with $m = O(\epsilon^{-2}\log n)$ for $n := |T|$. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within $T$ and not to $T$ from the rest of space. The downside of prior work is that evaluating their embedding on some $q\in \mathbb{R}^d$ required solving a semidefinite program with $\Theta(n)$ constraints in~$m$ variables and thus required some superlinear $\mathrm{poly}(n)$ runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process $T$ to obtain an almost linear-space data structure that supports computing the terminal embedding image of any $q\in\mathbb{R}^d$ in sublinear time $O^* (n^{1-\Theta(\epsilon^2)} + d)$. To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.]]> 0 Wed, 13 Mar 2024 08:14:57 +0000 https://doi.org/10.46298/theoretics.24.5 https://doi.org/10.46298/theoretics.24.5 Scheder, Dominik Scheder, Dominik 0 Wed, 13 Mar 2024 08:13:21 +0000 https://doi.org/10.46298/theoretics.24.4 https://doi.org/10.46298/theoretics.24.4 Cheval, Vincent Kremer, Steve Rakotonirina, Itsaka Cheval, Vincent Kremer, Steve Rakotonirina, Itsaka 0 Thu, 15 Feb 2024 09:43:52 +0000 https://doi.org/10.46298/theoretics.24.3 https://doi.org/10.46298/theoretics.24.3 Chen, Lijie Jin, Ce Santhanam, Rahul Williams, Ryan Chen, Lijie Jin, Ce Santhanam, Rahul Williams, Ryan 0 Tue, 06 Feb 2024 12:51:56 +0000 https://doi.org/10.46298/theoretics.24.2 https://doi.org/10.46298/theoretics.24.2 Hopkins, Max Kane, Daniel M. Lovett, Shachar Mahajan, Gaurav Hopkins, Max Kane, Daniel M. Lovett, Shachar Mahajan, Gaurav 0 Fri, 12 Jan 2024 10:54:23 +0000 https://doi.org/10.46298/theoretics.24.1 https://doi.org/10.46298/theoretics.24.1 Newman, Ilan Varma, Nithin Newman, Ilan Varma, Nithin 0 Wed, 10 Jan 2024 10:05:09 +0000 https://doi.org/10.46298/theoretics.23.11 https://doi.org/10.46298/theoretics.23.11 Place, Thomas Zeitoun, Marc Place, Thomas Zeitoun, Marc 0 Sat, 30 Dec 2023 13:11:14 +0000 https://doi.org/10.46298/theoretics.23.12 https://doi.org/10.46298/theoretics.23.12 Goldreich, Oded Ron, Dana Goldreich, Oded Ron, Dana 0 Tue, 26 Dec 2023 20:07:35 +0000 https://doi.org/10.46298/theoretics.23.10 https://doi.org/10.46298/theoretics.23.10 Eppstein, David Eppstein, David 0 Fri, 25 Aug 2023 11:48:34 +0000 https://doi.org/10.46298/theoretics.23.9 https://doi.org/10.46298/theoretics.23.9 Assadi, Sepehr Kumar, Pankaj Mittal, Parth Assadi, Sepehr Kumar, Pankaj Mittal, Parth 0 Mon, 19 Jun 2023 07:10:09 +0000 https://doi.org/10.46298/theoretics.23.8 https://doi.org/10.46298/theoretics.23.8 Alon, Noga Gonen, Alon Hazan, Elad Moran, Shay Alon, Noga Gonen, Alon Hazan, Elad Moran, Shay 0 Thu, 15 Jun 2023 11:51:42 +0000 https://doi.org/10.46298/theoretics.23.7 https://doi.org/10.46298/theoretics.23.7 Feng, Weiming Guo, Heng Jerrum, Mark Wang, Jiaheng Feng, Weiming Guo, Heng Jerrum, Mark Wang, Jiaheng 0 Tue, 02 May 2023 11:15:27 +0000 https://doi.org/10.46298/theoretics.23.6 https://doi.org/10.46298/theoretics.23.6 Huang, Shang-En Huang, Dawei Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel Huang, Shang-En Huang, Dawei Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel 0 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of some fixed Hamming weight $k\in [q,n-q]$ must also vanish at all points in $\{0,1\}^n$ of weight $k + q$. This lemma was used by Heged\H{u}s (2009) to give a solution to \emph{Galvin's problem}, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-$2$ threshold circuits for computing some symmetric functions. In this paper, we formulate a robust version of Heged\H{u}s's lemma. Informally, this version says that if a polynomial of degree $o(q)$ vanishes at most points of weight $k$, then it vanishes at many points of weight $k+q$. We prove this lemma and give three different applications.]]> Wed, 01 Mar 2023 14:47:30 +0000 https://doi.org/10.46298/theoretics.23.5 https://doi.org/10.46298/theoretics.23.5 Srinivasan, Srikanth Srinivasan, Srikanth 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of some fixed Hamming weight $k\in [q,n-q]$ must also vanish at all points in $\{0,1\}^n$ of weight $k + q$. This lemma was used by Heged\H{u}s (2009) to give a solution to \emph{Galvin's problem}, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-$2$ threshold circuits for computing some symmetric functions. In this paper, we formulate a robust version of Heged\H{u}s's lemma. Informally, this version says that if a polynomial of degree $o(q)$ vanishes at most points of weight $k$, then it vanishes at many points of weight $k+q$. We prove this lemma and give three different applications.]]> 0 Fri, 24 Feb 2023 13:39:08 +0000 https://doi.org/10.46298/theoretics.23.4 https://doi.org/10.46298/theoretics.23.4 Banerjee, Tamajit Majumdar, Rupak Mallik, Kaushik Schmuck, Anne-Kathrin Soudjani, Sadegh Banerjee, Tamajit Majumdar, Rupak Mallik, Kaushik Schmuck, Anne-Kathrin Soudjani, Sadegh 0 Tue, 31 Jan 2023 08:56:28 +0000 https://doi.org/10.46298/theoretics.23.3 https://doi.org/10.46298/theoretics.23.3 Ohlmann, Pierre Ohlmann, Pierre 0 0$, it has polymorphisms where each coordinate has Shapley value at most $\epsilon$, else it is NP-hard. The algorithmic part of our dichotomy is based on a structural lemma that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. Of independent interest, we show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.]]> Wed, 25 Jan 2023 08:45:00 +0000 https://doi.org/10.46298/theoretics.23.2 https://doi.org/10.46298/theoretics.23.2 Brakensiek, Joshua Guruswami, Venkatesan Sandeep, Sai Brakensiek, Joshua Guruswami, Venkatesan Sandeep, Sai 0$, it has polymorphisms where each coordinate has Shapley value at most $\epsilon$, else it is NP-hard. The algorithmic part of our dichotomy is based on a structural lemma that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. Of independent interest, we show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.]]> 0 Mon, 16 Jan 2023 09:15:47 +0000 https://doi.org/10.46298/theoretics.23.1 https://doi.org/10.46298/theoretics.23.1 Bouyer, Patricia Randour, Mickael Vandenhove, Pierre Bouyer, Patricia Randour, Mickael Vandenhove, Pierre 0 0$. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.]]> Wed, 21 Dec 2022 11:29:42 +0000 https://doi.org/10.46298/theoretics.22.2 https://doi.org/10.46298/theoretics.22.2 Austrin, Per Risse, Kilian Austrin, Per Risse, Kilian 0$. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.]]> 0 Wed, 21 Dec 2022 11:27:11 +0000 https://doi.org/10.46298/theoretics.22.1 https://doi.org/10.46298/theoretics.22.1 Goldreich, Oded Wigderson, Avi Goldreich, Oded Wigderson, Avi 0