Pith. sign in

REVIEW 2 major objections 6 minor 50 references

Improved Differentially Private Continual Observation Using Group Algebra

T0 review · 2 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Explicit factorization of weighted prefix sums matches best non-constructive error bound.

desk verdict Novel group-algebra framing for continual observation, but the central factorization is false as written; the idea may be repairable but the current proof does not work. read the letter →

arxiv 2412.02840 v2 pith:BZ6XXSS5 submitted 2024-12-03 cs.DS

Monika Henzinger , Jalaj Upadhyay This is my paper · ORCID
classification cs.DS MSC 68P2715A6015B05
keywords differentialprivacycontinualobservationfactorizationnormsmatrixmechanismgroup-patternmatricesweightedprefixsumsslidingwindowToeplitz
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to prove that every weighted prefix-sum matrix $M_f$ -- the lower-triangular matrix whose entries are $f(i-j)$ for $i\ge j$ -- has an explicit, efficiently computable factorization $M_f=LR$ whose factorization norm is at most $\frac{1}{2n^{1-1/p}}\sum_{\ell=0}^{2n-1}|m_f(\omega^\ell)|$, where $m_f(x)=\sum_{k=0}^{n-1}f(k)x^k$ and $\omega$ is a primitive $2n$-th root of unity. This matters because factorization norms control the additive error of the Gaussian matrix mechanism used to release weighted prefix sums under differential privacy: smaller norm means smaller noise for the same privacy guarantee. If the claim is correct, the construction matches the best-known non-constructive upper bound for the unweighted counting matrix, gives the first explicit factorization for sliding-window matrices, and works for arbitrary real-valued weight functions rather than only monotone positive ones. The motivating application is production private next-word prediction, where the weighted-sum step multiplies the model dimension and any constant-factor improvement in noise is practically significant.

What carries the argument

The load-bearing object is the group-pattern matrix: given a finite group $G$ with listed elements $g_1,\dots,g_k$ and a function $h:G\to\mathbb{C}$, the matrix has $(i,j)$-entry $h(g_i^{-1}g_j)$. The paper uses the cyclic group of $2n$-th roots of unity, defines $h=a_f$ as in eq. (13), and applies the group-product theorem that a product of two group-pattern matrices is again a group-pattern matrix with the convolution of their defining functions. The proof sets the two factor functions to the square root, $b_f(x)=c_f(x)=\frac{1}{2n}\sum_{\ell=0}^{2n-1}\sqrt{m_f(\omega^\ell)}\,x^\ell$, takes the right factor to be the conjugate transpose of the left factor, and then uses the orthogonality of roots of unity. The theorem converts the entire factorization problem into one scalar identity on the group, which is why the final bound is just an average of $|m_f(\omega^\ell)|$ and why no convex program is needed.

What would settle it

Take $n=3$ with $f(0)=1$, $f(1)=2$, $f(2)=4$; then $M_f[2,1]=2$ and $M_f[1,2]=0$. Constructing $\tilde L$ by eq. (17) with $b_f$ from eq. (16) forces the product $\tilde L\tilde L^*$ to be Hermitian, so its $(1,2)$ and $(2,1)$ entries are equal and it cannot equal the non-symmetric $M_f$; checking this entry pair for any non-symmetric $f$ settles the factorization identity as written.

Watch

Extended reading notes

Core claim

The core discovery is a new route from weighted prefix sums to group algebra. The paper embeds the $n\times n$ Toeplitz matrix $M_f$ as a principal submatrix of a $2n\times 2n$ group-pattern matrix built from a cyclic group of order $2n$: with $\omega$ a primitive $2n$-th root of unity and $a_f(x)=\frac{1}{2n}\sum_{\ell=0}^{2n-1}m_f(\omega^\ell)x^\ell$, the entry $a_f(\omega^{j-i})$ reproduces $M_f$ on the first $n$ rows and columns. The factorization is obtained by writing $b_f(x)=c_f(x)=\frac{1}{2n}\sum_{\ell=0}^{2n-1}\sqrt{m_f(\omega^\ell)}\,x^\ell$ and using the theorem that the product of two group-pattern matrices is again a group-pattern matrix whose defining function is the group convolution of the two functions. The factors are then converted from complex to real and made lower-triangular by an orthogonal-triangular decomposition, yielding an explicit algorithm rather than a convex optimization. The result is a single average bound for all $\gamma^{(p)}(M_f)$, $p\in[2,\infty)$, stated directly in terms of the values of the weight polynomial on the roots of unity.

Load-bearing premise

The proof assumes that the right factor can be taken as the conjugate transpose of the left factor, but for a real matrix $M_f$ this makes the product necessarily symmetric while $M_f$ is lower-triangular and generally not symmetric, so the equality can hold only in special cases.

Editorial extensions

If this is right

  • For the unweighted counting matrix, $\gamma_2(M_{\text{count}}) \le 1+\ln(n)/\pi$, matching the best-known non-constructive upper bound and improving the previous constructive bound by the Euler-Mascheroni constant divided by $\pi$.
  • For the sliding-window matrix with window size $W$, the bound $\gamma_2(M_{\text{sliding}}) \le \frac{1}{2n}\sum_{\ell=0}^{2n-1}\left|\frac{1-\omega^{W\ell}}{1-\omega^\ell}\right|$ is the first explicit factorization and upper bound for this matrix.
  • For the $b$-striped matrix, $\gamma_2(M_{\text{striped}}) \le 1+\frac{1}{\pi}\ln(n/b)$, improving the previous constructive bound by the same constant as in the counting case.
  • For any real-valued weight function $f$ and any $p\ge 2$, the paper's mechanism has $\ell_p$ error at most $\sigma_{\epsilon,\delta}\min\{\sqrt{p},\sqrt{\ln n}\}\cdot \frac{1}{2n^{1-1/p}}\sum_{\ell=0}^{2n-1}|m_f(\omega^\ell)|$, so the same bound controls both expected error and high-probability tails.
  • The construction removes the monotonicity and positivity restrictions of earlier weighted-sum frameworks, so windowed, striped, and arbitrary real-valued weight functions are handled by the same explicit factorization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is to minimize the same average over other cyclic groups of order $2n$: the paper's remark allows any generator $g$, so one can search for the generator minimizing $\sum_\ell |m_f(g^\ell)|$ and potentially beat the root-of-unity choice for structured weight functions.
  • Because the bound is a Fourier average of the weight function, it suggests a design heuristic for private weighted sums: weight functions with small discrete Fourier magnitudes on the $2n$-th roots of unity have small additive error, so approximating a desired weight function by one with such a spectrum could reduce noise before privacy is applied.
  • The same lifting applies to any linear query matrix that is a principal submatrix of a group-pattern matrix, not just Toeplitz prefix sums; candidates include circulant or near-circulant query families, for which the group-convolution theorem would supply an explicit factorization without optimization.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes a group-algebra approach to explicitly factor lower-triangular Toeplitz matrices M_f arising in differentially private weighted prefix sums under continual observation. The authors view M_f as a principal submatrix of a 2n×2n group-pattern matrix over the 2n-th roots of unity, define polynomials a_f and b_f from the evaluations of the symbol m_f(ω^ℓ), and claim a factorization M_f = eL eR with the norm bound γ^(p)(M_f) ≤ (1/(2n^{1-1/p})) Σ_{ℓ=0}^{2n-1} |m_f(ω^ℓ)|. This is used to derive improved upper bounds for counting, sliding-window, and striped matrices, and to instantiate the matrix mechanism for differentially private continual observation.

Significance. If the main theorem were correct, the paper would give the first explicit factorization matching the best-known non-constructive γ₂ bound for the counting matrix, improve on prior constructive factorizations, and provide the first upper bound for the sliding-window matrix for arbitrary real weight functions. The group-algebra viewpoint is a fresh and potentially reusable idea, and the intended Algorithm 1 is genuinely explicit. However, the central algebraic identity in Section 3.1.2 is false as written, and a cited theorem in Section 2.2.3 is misstated; consequently the main claims are not currently established despite the elegance of the approach.

major comments (2)
  1. [Section 3.1.2, Eq. (17)] The claimed factorization M_f = eL eR is false under the definitions given. Since eR is set to eL* (the conjugate transpose), the product eL eR = eL eL* is Hermitian, while M_f is lower-triangular Toeplitz and is not Hermitian in general: for n = 2 and f(0) = f(1) = 1, M_f = [[1,0],[1,1]] is not Hermitian. Thus the identity used to prove Theorem 1.1 and the correctness of Algorithm 1 does not hold. The subsequent step '(eL[j,i])* = bf(ω^{j-i})' is also unjustified: for bf(x) = (1/2n) Σ ζ_ℓ x^ℓ, the conjugate of bf(ω^{i-j}) equals (1/2n) Σ conj(ζ_ℓ) ω^{ℓ(j-i)}, which equals bf(ω^{j-i}) only if every ζ_ℓ is real, and ζ_ℓ = sqrt(mf(ω^ℓ)) is generally complex. A correct right factor would be the group-pattern matrix with entries eR[i,j] = bf(ω^{j-i}) for 1 ≤ i ≤ 2n and 1 ≤ j ≤ n; with that choice the group-convolution identity (15) would apply, but the norm estimates in Claims 3.1 and 3.2 would need to be re-derived for the new eR rather than following from eR = eL*.
  2. [Section 2.2.3, Theorem 2.5] Theorem 2.5 misstates the direction of Mathias's bound. The displayed quantity with n = 2 equals (3/4)(|csc(π/4)| + |csc(3π/4)|) = (3/4)·2√2 ≈ 2.12, but γ₂(M_count) ≤ √2 via the trivial factorization M_count = [[1,0],[1,1]]·I, so the bound cannot be a lower bound; in Mathias's paper Corollary 3.5 is an upper bound on γ₂(M_count). This error propagates directly into Theorem 6.1, where the first term in eq. (25) is asserted as a lower bound on γ₂(M_sliding) and is not valid; only the Matoušek et al. lower bound in eq. (10) is valid. Please correct the direction of Theorem 2.5, update the discussion in Section 1.2 and Remark 1.3, and revise Theorem 6.1 accordingly.
minor comments (6)
  1. [Title and Abstract] There are typos in the title and abstract ('DIFFERENTIALL Y PRIV A TE', 'Differentiall y'); these should be corrected.
  2. [Section 1, Definition of F] The set F is introduced as 'non-negative valued functions', but Theorem 1.1 and the introduction claim the result for all real-valued f; please reconcile the domain of the theorem with the definition of F.
  3. [Section 5 and Corollary 1.1] For the sliding-window matrix, Eq. (5) defines M_sliding[i,j] = 1 for 0 ≤ i−j ≤ W, which gives W+1 nonzero diagonals, while the text writes the polynomial as 1 + x + ... + x^{W−1} and the bound uses the numerator 1−ω^{Wℓ}; this off-by-one discrepancy should be fixed and the bounds restated consistently.
  4. [Section 3.2, proof of Eq. (14)] In the first case of the proof of Eq. (14), the term for k = d is written as 'Σ_{ℓ=0}^{2n-1} f(d)' but should be '2n·f(d)' before division by 2n; this is a typographical slip in an otherwise clear calculation.
  5. [Section 4.1 and Algorithm 1, line 3] The real-valued factor bR is defined in Eq. (21) as a vertical stacking of eRr and −eRc, but Algorithm 1 writes 'bR = [ eRr − eRc ]*' with a star, which is inconsistent with the surrounding text and notation; please align the algorithm with Eq. (21).
  6. [Theorem 1.2 vs. Definition 2.1] Eq. (8) uses σ_{ε,δ} = (2Δ/ε)√ln(1.25/δ), while Definition 2.1 and Theorem 2.7 use a different expression σ_{ε,δ} = (2/ε)√(4/9 + ln((1/δ)√(2/π))); the paper should state which Gaussian mechanism is being used and ensure the constants are consistent throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the factorization and norm bound are explicit constructions from f, not restatements of the input.

full rationale

The paper's central derivation is self-contained rather than circular. Theorem 1.1 constructs the factorization explicitly: eq. (13) defines the polynomial af from the input f, eq. (16) defines the factor polynomial bf from the evaluations mf(omega^ell), and eq. (17) defines the matrices eL and eR directly from bf. The claimed bound on gamma^(p)(Mf) is then obtained by direct computation of Tr_p(eL) and ||eR||_{1->2} in Claims 3.1 and 3.2 and eq. (20); these quantities are not fitted parameters and are neither assumed nor equivalent to the factorization norm being bounded. The cited results (Mathias, Matousek-Nikolov-Talwar, Haagerup, Denisov et al.) are external comparisons or standard tools, not self-referential supports for the main inequality. The self-citations to Fichtenberger-Henzinger-Upadhyay and Henzinger-Upadhyay-Upadhyay are used only to compare against prior bounds and to motivate the technique, not to justify the new factorization. The paper's apparent weaknesses are algebraic correctness issues (e.g., setting eR = eL* makes eL eR Hermitian while Mf is lower-triangular, and the direction of Mathias's inequality in Theorem 2.5 appears misquoted), which are errors in the proof rather than instances of assuming the conclusion. The derivation does not rename a known result: it supplies an explicit L and R and computes their norms from first principles. Accordingly, no circular step meets the evidentiary standard of this review.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters and no invented entities. Its main construction depends on the erroneous identity eR=eL^*, on the standard group-pattern product theorem, and on prior results for Gaussian mechanisms and factorization norms. The false Mathias bound is treated as an additional unsupported premise in the tightness section.

assumptions (4)
  • ad hoc to paper The right factor in the group-pattern factorization can be set to the conjugate transpose of the left factor (eR = eL^*).
    Invoked in Section 3.1.2 before eq. (17); this assumption is false for complex square roots and breaks the factorization.
  • standard math Group-pattern product theorem (Theorem 2.3) applies to the rectangular n×2n and 2n×n factors and yields the principal submatrix M_f.
    Theorems from Chalkley; the application is standard if the right factor is chosen correctly, but as used it inherits the eR=eL^* error.
  • standard math The Gaussian mechanism and the factorization-norm error bound of eq. (7) from prior work.
    Used in Theorems 1.2 and Corollary 1.1; these are established results in differential privacy.
  • ad hoc to paper Mathias's lower bound as stated in Theorem 2.5.
    The stated bound contradicts the trivial factorization M=I·M for n=2; it appears to be a misstatement and is used in Theorem 6.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Differentially Private Continual Observation Using Group Algebra." pith.science (2026). https://pith.science/paper/BZ6XXSS5

@misc{pith2026241202840,
  author       = {Pith},
  title        = {Pith review of: Improved Differentially Private Continual Observation Using Group Algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BZ6XXSS5}},
  note         = {Machine review of arXiv:2412.02840}
}
abstract

Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which, according to Google, has over a billion users. More specifically, Google uses a differentially private mechanism to sum weighted gradients in its \emph{private follow-the-regularized leader} algorithm. Apart from efficiency, the additive error of the private mechanism is crucial as multiplied with the square root of the model's dimension $d$ (with $d$ ranging up to $10$ trillion, for example, Switch Transformers or M6-10T), it determines the accuracy of the learning system. So, any improvement in leading constant matters significantly in practice. In this paper, we show a novel connection between mechanisms for continual weighted prefix sum and a concept in representation theory known as the group matrix introduced in correspondence between Dedekind and Frobenius (1897) and generalized by Schur (1904). To the best of our knowledge, this is the first application of group algebra to analyze differentially private algorithms. Using this connection, we analyze a class of matrix norms known as {\em factorization norms} that give upper and lower bounds for the additive error under general $\ell_p$-norms of the matrix mechanism. This allows us to give the first efficient factorization that matches the best-known non-constructive upper bound on the factorization norm by Mathias (1993) for the matrix used in Google's deployment and also improves on the previous best-known constructive bound of Fichtenberger et al. (ICML 2023) and Henzinger et al. (SODA 2023) and the first upper bound on the additive error for a large class of weight functions for weighted prefix sum problems, including the sliding window matrix (Bolot et al. (ICDT 2013).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 45 canonical work pages

  1. [1]

    Triangular projection on Sp, 0 < p <1 and related inequalities

    A Aleksandrov and V Peller. Triangular projection on Sp, 0 < p <1 and related inequalities. Proceedings of the American Mathematical Society, 151(06):2559–2571, 2023

    work page 2023

  2. [2]

    A smooth binary mechanism for efficient private continual observation

    Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. In Neural Information Processing Letters, 2023

    work page 2023

  3. [3]

    Improved counting under continual observation with pure differential privacy

    Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy. arXiv preprint arXiv:2408.07021 , 2024

    arXiv 2024

  4. [4]

    Plan: variance-aware private mean estimation

    Martin Aum¨ uller, Christian Janos Lebeda, Boel Nelson, and Rasmus Pagh. Plan: variance-aware private mean estimation. arXiv preprint arXiv:2306.08745 , 2023

    arXiv 2023

  5. [5]

    Schur multipliers

    G Bennett. Schur multipliers. Duke Mathematics I , 44:603–639, 1977

    work page 1977

  6. [6]

    Private decayed predicate sums on streams

    Jean Bolot, Nadia Fawaz, Shan Muthukrishnan, Aleksandar Nikolov, and Nina Taft. Private decayed predicate sums on streams. In Proceedings of the 16th International Conference on Database Theory, pages 284–295. ACM, 2013

    work page 2013

  7. [7]

    Toeplitz matrices, asymptotic linear algebra and functional analysis , volume 67

    Albrecht B¨ ottcher and Sergei M Grudsky. Toeplitz matrices, asymptotic linear algebra and functional analysis , volume 67. Springer, 2000

    work page 2000

  8. [8]

    Differentially private histograms under continual observation: Stream- ing selection into the unknown

    Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Stream- ing selection into the unknown. In International Conference on Artificial Intelligence and Statistics , pages 2397–

    work page

Show all 50 references
  1. [9]

    https://www.cdc.gov/coronavirus/2019-ncov/index.html, 2020

    CDC. https://www.cdc.gov/coronavirus/2019-ncov/index.html, 2020

    2019

  2. [10]

    A matrix-oriented approach to group algebras, 1976

    Roger Chalkley. A matrix-oriented approach to group algebras, 1976

    1976

  3. [11]

    Differentially private continual monitoring of heavy hitters from distributed streams

    T-H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially private continual monitoring of heavy hitters from distributed streams. In International Symposium on Privacy Enhancing Technologies Symposium , pages 140–159. Springer, 2012

    2012

  4. [12]

    Hubert Chan, Elaine Shi, and Dawn Song

    T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011

    2011

  5. [13]

    Choquette-Choo, Hugh Brendan McMahan, J

    Christopher A. Choquette-Choo, Hugh Brendan McMahan, J. Keith Rush, and Abhradeep Guha Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research,...

    2023

  6. [14]

    Maintaining time-decaying stream aggregates

    Edith Cohen and Martin Strauss. Maintaining time-decaying stream aggregates. In Proceedings of the twenty- second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages 223–233, 2003

    2003

  7. [15]

    Davidson

    Kenneth R. Davidson. Nest Algebras. Pitman Research Notes in Mathematical Sciences, vol. 191, 1988

    1988

  8. [16]

    Aus briefen an Frobenius https://rcin.org.pl/dlibra/publication/171804/edition/ 140750/content, 1882

    Richard Dedekind. Aus briefen an Frobenius https://rcin.org.pl/dlibra/publication/171804/edition/ 140750/content, 1882

  9. [17]

    Smith, and Abhradeep G

    Sergey Denisov, Brendan McMahan, Keith Rush, Adam D. Smith, and Abhradeep G. Thakurta. Improved differ- ential privacy for sgd via optimal private linear operators on adaptive streams. arXiv preprint arXiv:2202.08312, 2022

    2022 arXiv

  10. [18]

    Making old things new: a unified algorithm for differentially private clustering

    Max Dupr´ e la Tour, Monika Henzinger, and David Saulpic. Making old things new: a unified algorithm for differentially private clustering. In Proc. 41th ICML , 2024. 19

    2024

  11. [19]

    Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta

    Krishnamurthy (Dj) Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Foundations of Com- puter Science, 2024

    2024

  12. [20]

    Our data, ourselves: Privacy via distributed noise generation

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology-EUROCRYPT , pages 486–503. Springer, 2006

    2006

  13. [21]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality , 7(3):17–51, 2016

    2016

  14. [22]

    Rothblum

    Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual obser- vation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC’10) , pages 715–724, 2010

    2010

  15. [23]

    The power of factorization mechanisms in local and central differential privacy

    Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 425–438, 2020

    2020

  16. [24]

    The characteristic roots of certain real symmetric matrices

    Joseph Frederick Elliott. The characteristic roots of certain real symmetric matrices. Master of Science , 1953

    1953

  17. [25]

    Differentially private continual releases of streaming frequency moment estimations

    Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 , pages 4...

    2023

  18. [26]

    Differentially private algorithms for graphs under continual observation

    Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms, ESA , 2021

    2021

  19. [27]

    Constant matters: Fine-grained error bound on differentially private continual observation

    Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning , pages 10072– 10092. PMLR, 2023

    2023

  20. [28]

    Symplectic capacity and the main triangle projection.St

    E Gluskin. Symplectic capacity and the main triangle projection.St. Petersburg Mathematical Journal, 30(3):437– 443, 2019

    2019

  21. [29]

    Yehoram Gordon and D. R. Lewis. Absolutely summing operators and local unconditional structures. Acta Mathematica, 133:27–48, 1974

    1974

  22. [30]

    Decomposition of completely bounded maps on operator algebras, 1980

    Uffe Haagerup. Decomposition of completely bounded maps on operator algebras, 1980

    1980

  23. [31]

    Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Private counting of distinct elements in the turnstile model and extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 317 of LIPIcs, pages 40:1–...

    2024

  24. [32]

    Differentially private data structures under continual observation for histograms and related queries

    Monika Henzinger, AR Sricharan, and Teresa Anna Steiner. Differentially private data structures under continual observation for histograms and related queries. arXiv preprint arXiv:2302.11341 , 2023

    2023 arXiv

  25. [33]

    Almost tight error bounds on differentially private continual counting

    Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 5003–5039, 2023

    2023

  26. [34]

    A unifying framework for differentially private sums under continual observation

    Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for differentially private sums under continual observation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 995–1018, 2024

    2024

  27. [35]

    Efficient use of differentially private binary trees

    James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK , 2015

    2015

  28. [36]

    The price of differential privacy under continual observation

    Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In International Conference on Machine Learning, ICML 2023 , pages 14654–14678, 2023

    2023

  29. [37]

    On the best constants in some non-commutative martingale inequalities.Bulletin of the London Mathematical Society , 37(2):243–253, 2005

    Marius Junge and Quanhua Xu. On the best constants in some non-commutative martingale inequalities.Bulletin of the London Mathematical Society , 37(2):243–253, 2005

    2005

  30. [38]

    Continuity of the map S → |S| for linear operators

    Tosio Kato. Continuity of the map S → |S| for linear operators. Proceedings of the Japan Academy, 49(3):157– 160, 1973

    1973

  31. [39]

    The main triangle projection in matrix spaces and its applications

    Stanis law Kwapie´ n and Aleksander Pe lczy´ nski. The main triangle projection in matrix spaces and its applications. Studia Mathematica, 34(1):43–67, 1970

    1970

  32. [40]

    Diffrentially Private Release of Sparse and Skewed Data

    Christian Janos Lebeda. Diffrentially Private Release of Sparse and Skewed Data . IT University of Copenhagen, Department of computer science, 2023

    2023

  33. [41]

    The matrix mechanism: opti- mizing linear counting queries under differential privacy

    Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: opti- mizing linear counting queries under differential privacy. The VLDB journal , 24(6):757–781, 2015

    2015

  34. [42]

    Optimality of matrix mechanism on ℓp p-metric

    Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimality of matrix mechanism on ℓp p-metric. arXiv preprint arXiv:2406.02140, 2024

    2024 arXiv

  35. [43]

    The hadamard operator norm of a circulant and applications

    Roy Mathias. The hadamard operator norm of a circulant and applications. SIAM journal on matrix analysis and applications, 14(4):1152–1167, 1993

    1993

  36. [44]

    Factorization norms and hereditary discrepancy.Inter- national Mathematics Research Notices , 2020(3):751–780, 2020

    Jiˇ r ´ ı Matouˇ sek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy.Inter- national Mathematics Research Notices , 2020(3):751–780, 2020. 20

    2020

  37. [45]

    Federated learning with formal differential privacy guarantees

    Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy guarantees. Google AI Blog, 2022

    2022

  38. [46]

    General gaussian noise mechanisms and their optimality for unbiased mean estimation

    Aleksandar Nikolov and Haohua Tang. General gaussian noise mechanisms and their optimality for unbiased mean estimation. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024 , pages 85:1– 85:23, 2024

    2024

  39. [47]

    The formula of faa di bruno

    Steven Roman. The formula of faa di bruno. The American Mathematical Monthly , 87(10):805–809, 1980

    1980

  40. [48]

    Sublinear space private algorithms under the sliding window model

    Jalaj Upadhyay. Sublinear space private algorithms under the sliding window model. In International Conference on Machine Learning , pages 6363–6372, 2019

    2019

  41. [49]

    Differentially private analysis on graph streams

    Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In International Conference on Artificial Intelligence and Statistics , pages 1171–1179. PMLR, 2021

    2021

  42. [50]

    Several proofs of the irreducibility of the cyclotomic polynomials

    Steven H Weintraub. Several proofs of the irreducibility of the cyclotomic polynomials. The American Mathe- matical Monthly, 120(6):537–545, 2013. Appendix A. Auxiliary Lemmata F act A.1 (Half angle formula) . Let θ ∈ R. Then cos(2θ) = 1 − 2 sin2(θ) and sin(2θ) = 2 sin(θ) cos(...

    2013

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.