Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Cheung, Tsun Ming ; Hatami, Hamed ; Hosseini, Kaave ; Nikolov, Aleksandar ; Pitassi, Toniann and Shirley, Morgan LU orcid (2026) In Algorithmica 88(4).
Abstract

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-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.

Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Communication complexity, Complexity theory, Fourier spectral norm, Parity decision tree, Query complexity, Sidon set, γ Norm
in
Algorithmica
volume
88
issue
4
article number
54
publisher
Springer
external identifiers
  • scopus:105041093594
ISSN
0178-4617
DOI
10.1007/s00453-026-01396-2
language
English
LU publication?
yes
id
0e71ab92-7e80-4c10-a485-eb027aac5b7b
date added to LUP
2026-07-02 13:19:59
date last changed
2026-07-02 13:19:59
@article{0e71ab92-7e80-4c10-a485-eb027aac5b7b,
  abstract     = {{<p>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-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.</p>}},
  author       = {{Cheung, Tsun Ming and Hatami, Hamed and Hosseini, Kaave and Nikolov, Aleksandar and Pitassi, Toniann and Shirley, Morgan}},
  issn         = {{0178-4617}},
  keywords     = {{Communication complexity; Complexity theory; Fourier spectral norm; Parity decision tree; Query complexity; Sidon set; γ Norm}},
  language     = {{eng}},
  number       = {{4}},
  publisher    = {{Springer}},
  series       = {{Algorithmica}},
  title        = {{A Lower Bound on the Trace Norm of Boolean Matrices and its Applications}},
  url          = {{http://dx.doi.org/10.1007/s00453-026-01396-2}},
  doi          = {{10.1007/s00453-026-01396-2}},
  volume       = {{88}},
  year         = {{2026}},
}