The Wrong Direction of Jensen’s Inequality Is Algorithmically Right

Zamir, Or

doi:10.4230/LIPIcs.ICALP.2023.107

File

PDF

LIPIcs.ICALP.2023.107.pdf

Filesize: 0.6 MB
10 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ICALP.2023.107
URN: urn:nbn:de:0030-drops-181593

Subject Classification

ACM Subject Classification

Theory of computation → Parameterized complexity and exact algorithms
Theory of computation → Algorithm design techniques
Theory of computation → Computational complexity and cryptography

Keywords

algorithms
complexity
Jensen’s inequality

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

Let 𝒜 be an algorithm with expected running time e^X, conditioned on the value of some random variable X. We construct an algorithm A' with expected running time O (e^𝖤[X]), that fully executes 𝒜. In particular, an algorithm whose running time is a random variable T can be converted to one with expected running time O (e^𝖤[ln T]), which is never worse than O(𝖤[T]). No information about the distribution of X is required for the construction of 𝒜'.

Cite As Get BibTex

Or Zamir. The Wrong Direction of Jensen’s Inequality Is Algorithmically Right. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 107:1-107:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.107

Author Details

Or Zamir

Princeton University, NJ, USA

Acknowledgements

The author would like to thank Avi Wigderson for pointing out important references.

References

Helmut Alt, Leonidas Guibas, Kurt Mehlhorn, Richard Karp, and Avi Wigderson. A method for obtaining randomized algorithms with small tail probabilities. Algorithmica, 16(4):543-547, 1996.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-sat algorithms using biased-ppsz. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 578-589, 2019.
Timon Hertli. 3-sat faster and simpler - unique-sat bounds for ppsz hold in general. SIAM Journal on Computing, 43(2):718-729, 2014.
Michael Luby, Alistair Sinclair, and David Zuckerman. Optimal speedup of las vegas algorithms. Information Processing Letters, 47(4):173-180, 1993.
Robin A Moser and Dominik Scheder. A full derandomization of schöning’s k-sat algorithm. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 245-252, 2011.
Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane. An improved exponential-time algorithm for k-sat. Journal of the ACM (JACM), 52(3):337-364, 2005.
Dominik Scheder. Ppsz is better than you think. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 205-216. IEEE, 2022.
T Schoning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 410-414. IEEE, 1999.
Or Zamir. Faster algorithm for unique (k, 2)-csp. ESA, 2022.