EUVIMEDEUVIMED entdecken
Crossref

A Lower Bound on the Trace Norm of Boolean Matrices and its Applications

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley

Algorithmica · 2026-08 · 88 (4)

DOI: 10.1007/s00453-026-01396-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 08.06.2026. Verfasst von Tsun-Ming Cheung und 5 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: NSERC, Goergen Institute for Data Science at the University of Rochester.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a simple method based on a variant of Hölder’s inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier L1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_1$$\end{document}-norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini, and Shirley (CCC 2023). As immediate consequences, we obtain the following results.

Förderung

  • NSERC
  • Goergen Institute for Data Science at the University of Rochester

Zitieren

APA

Cheung, T., Hatami, H., Hosseini, K., Nikolov, A., Pitassi, T., & Shirley, M. (2026). A Lower Bound on the Trace Norm of Boolean Matrices and its Applications. Algorithmica, 88(4). https://doi.org/10.1007/s00453-026-01396-2

Vancouver

Cheung T, Hatami H, Hosseini K, Nikolov A, Pitassi T, Shirley M. A Lower Bound on the Trace Norm of Boolean Matrices and its Applications. Algorithmica. 2026;88(4). doi:10.1007/s00453-026-01396-2

BibTeX
@article{Cheung2026,
  author = {Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Nikolov, Aleksandar and Pitassi, Toniann and Shirley, Morgan},
  title = {A Lower Bound on the Trace Norm of Boolean Matrices and its Applications},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {4},
  doi = {10.1007/s00453-026-01396-2}
}
Kostenlos starten →