131 Search Results for "Sudan, Madhu"

Document
DOI: 10.4230/LIPIcs.STACS.2026.30
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2026.30,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.30},
  URN =		{urn:nbn:de:0030-drops-255194},
  doi =		{10.4230/LIPIcs.STACS.2026.30},
  annote =	{Keywords: Boolean Function, Isomorphism of Boolean Function, Fourier Analysis, Sublinear Algorithm, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.38
Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.
Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.47
On the Hardness of the One-Sided Code Sparsifier Problem

Authors: Elena Grigorescu and Alice Moayyedi

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The notion of code sparsification was introduced by Khanna, Putterman and Sudan (SODA 2024) as an analogue to the more established notion of cut sparsification in graphs and hypergraphs. In particular, for α ∈ (0,1), an (unweighted) one-sided α-sparsifier for a linear code 𝒞 ⊆ 𝐅₂ⁿ is a subset S ⊆ [n] such that the weight of each codeword projected onto the coordinates in S is preserved up to an α fraction. Recently, Gharan and Sahami (arXiv:2502.02799) show the existence of one-sided 1/2-sparsifiers of size n/2+O(√{kn}) for any linear code, where k is the dimension of 𝒞. In this paper, we consider the computational problem of finding a one-sided 1/2-sparsifier of minimal size, and show that it is NP-hard, via a reduction from the classical nearest codeword problem. We also show hardness of approximation results.
Cite as

Elena Grigorescu and Alice Moayyedi. On the Hardness of the One-Sided Code Sparsifier Problem. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 47:1-47:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grigorescu_et_al:LIPIcs.STACS.2026.47,
  author =	{Grigorescu, Elena and Moayyedi, Alice},
  title =	{{On the Hardness of the One-Sided Code Sparsifier Problem}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{47:1--47:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.47},
  URN =		{urn:nbn:de:0030-drops-255365},
  doi =		{10.4230/LIPIcs.STACS.2026.47},
  annote =	{Keywords: Code sparsifiers, NP-hardness, Approximation hardness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.42
Time and Space Efficient Deterministic List Decoding

Authors: Joshua Cook and Dana Moshkovitz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Error correcting codes encode messages by codewords in such a way that even if some of the codeword is corrupted, the message can be decoded. Typical decoding algorithms for error correcting codes either use linear space or quadratic time. A natural question is whether codes can be decoded in near-linear time and sub-linear space simultaneously. A recent result by Cook and Moshkovitz gave efficient decoders that can uniquely decode Reed-Muller and other codes from a constant fraction (less than half) of corruption. In this work, we address the problem of list decoding in near-linear time and sub-linear space. In the list decoding setting, most of the codeword is corrupted, and one wants to output a short list of potential messages that contains the true message. For any constants γ, τ > 0, we give decoders for Reed-Muller codes that can decode from 1-γ fraction of corruptions in time n^{1+τ} and space n^{τ}. Our decoders work by extending the iterative correction technique of Cook and Moshkovitz. However, that technique, which gradually decreases the number of corruptions in the message, was tailored to the unique decoding setting. We first identify an intermediate problem, codewords list recovery, for which we can make iterative correction work. We then show how to reduce general list decoding to the codewords list recovery problem in efficient time and space. The reduction relies on local correction and testing. In the codewords list recovery problem, the input consists of n unordered lists containing exactly the symbols from L codewords, where a small fraction of the lists is corrupted. The goal is to find the L codewords. In addition, we prove that any linear code with time-space efficient encoding or decoding must be local, in the sense that the codewords satisfy a local linear constraint. This rules out codes like Reed-Solomon from having time-space efficient encoding or decoding.
Cite as

Joshua Cook and Dana Moshkovitz. Time and Space Efficient Deterministic List Decoding. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 42:1-42:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.ITCS.2026.42,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Time and Space Efficient Deterministic List Decoding}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{42:1--42:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.42},
  URN =		{urn:nbn:de:0030-drops-253292},
  doi =		{10.4230/LIPIcs.ITCS.2026.42},
  annote =	{Keywords: Reed-Muller code, local correction, local testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.103
A General Framework for Low Soundness Homomorphism Testing

Authors: Tushant Mittal and Sourya Roy

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime. In this regime, we give the first constant-query tests for various families of groups. These include tests for: (i) homomorphisms between arbitrary cyclic groups, (ii) homomorphisms between any finite group and ℤ_p, (iii) automorphisms of dihedral and symmetric groups, (iv) inner automorphisms of non-abelian finite simple groups and extraspecial groups, and (v) testing linear characters of GL_n(F_q), and finite-dimensional Lie algebras over F_q. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between F_qⁿ and F_q. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as F_qⁿ). No tests were known for non-abelian groups. As an additional corollary, our framework gives combinatorial list decoding bounds for cyclic groups with list size dependence of O(ε^{-2}) (for agreement parameter ε). This improves upon the currently best-known bound of O(ε^{-105}) due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14].
Cite as

Tushant Mittal and Sourya Roy. A General Framework for Low Soundness Homomorphism Testing. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 103:1-103:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mittal_et_al:LIPIcs.ITCS.2026.103,
  author =	{Mittal, Tushant and Roy, Sourya},
  title =	{{A General Framework for Low Soundness Homomorphism Testing}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{103:1--103:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.103},
  URN =		{urn:nbn:de:0030-drops-253901},
  doi =		{10.4230/LIPIcs.ITCS.2026.103},
  annote =	{Keywords: Property Testing, Coding Theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.104
Dimension-Free Correlated Sampling for the Hypersimplex

Authors: Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) k ∈ [n], while maximizing the overlap of the sampled sets. Specifically, the expected difference between two output sets should be at most α times their input vectors' 𝓁₁ distance. A value of α = O(log n) is known to be achievable, due to Chen et al. (ICALP'17). We improve this factor to O(log k), independent of the ambient dimension n. Our algorithm satisfies other desirable properties, including (up to a log^* n factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling, and swift multi-scenario submodular welfare approximating reallocation.
Cite as

Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc. Dimension-Free Correlated Sampling for the Hypersimplex. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.ITCS.2026.104,
  author =	{Naor, Joseph (Seffi) and Raju, Nitya and Shetty, Abhishek and Srinivasan, Aravind and Valieva, Renata and Wajc, David},
  title =	{{Dimension-Free Correlated Sampling for the Hypersimplex}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.104},
  URN =		{urn:nbn:de:0030-drops-253918},
  doi =		{10.4230/LIPIcs.ITCS.2026.104},
  annote =	{Keywords: Correlated Rounding, Dependent Rounding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.106
List Decoding Reed-Solomon Codes in the Lee, Euclidean, and Other Metrics

Authors: Chris Peikert and Alexandra Veliche Hostetler

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Reed-Solomon error-correcting codes are ubiquitous across computer science and information theory, with applications in cryptography, computational complexity, communication and storage systems, and more. Most works on efficient error correction for these codes, like the celebrated Berlekamp-Welch unique decoder and the (Guruswami-)Sudan list decoders, are focused on measuring error in the Hamming metric, which simply counts the number of corrupted codeword symbols. However, for some applications, other metrics that depend on the specific values of the errors may be more appropriate. This work gives a polynomial-time algorithm that list decodes (generalized) Reed-Solomon codes over prime fields in 𝓁_p (semi)metrics, for any 0 < p ≤ 2. Compared to prior algorithms for the Lee (𝓁₁) and Euclidean (𝓁₂) metrics, ours decodes to arbitrarily large distances (for correspondingly small rates), and has better distance-rate tradeoffs for all decoding distances above some moderate thresholds. We also prove lower bounds on the 𝓁₁ and 𝓁₂ minimum distances of a certain natural subclass of GRS codes, which establishes that our list decoder is actually a unique decoder for many parameters of interest. Finally, we analyze our algorithm’s performance under random Laplacian and Gaussian errors, and show that it supports even larger rates than for corresponding amounts of worst-case error in 𝓁₁ and 𝓁₂ (respectively).
Cite as

Chris Peikert and Alexandra Veliche Hostetler. List Decoding Reed-Solomon Codes in the Lee, Euclidean, and Other Metrics. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{peikert_et_al:LIPIcs.ITCS.2026.106,
  author =	{Peikert, Chris and Hostetler, Alexandra Veliche},
  title =	{{List Decoding Reed-Solomon Codes in the Lee, Euclidean, and Other Metrics}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{106:1--106:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.106},
  URN =		{urn:nbn:de:0030-drops-253932},
  doi =		{10.4230/LIPIcs.ITCS.2026.106},
  annote =	{Keywords: Reed-Solomon codes, list decoding, unique decoding, Lee metric, Euclidean metric, Guruswami-Sudan algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.15
How to Use Nondeterminism in Cryptography

Authors: Marshall Ball and Peter Crawford-Kahrl

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Nondeterministic reductions have yielded powerful results in the theory of computational complexity, yet are effectively useless in a cryptographic context. The reason for this is simple, a nondeterministic polynomial time adversary can trivially break almost any cryptographic primitive by simply guessing the "key." In order to use this powerful nondeterministic tool kit in the cryptographic context, we initiate the study of cryptography against adversaries with limited nondeterminism: polynomial time nondeterministic algorithms that are restricted to just a few bits of nondeterminism. We demonstrate that limited nondeterministic security is sufficient to prove two foundational results that have eluded our grasp for decades: dream hardness amplification, and extracting ω(log n) hardcore bits.
Cite as

Marshall Ball and Peter Crawford-Kahrl. How to Use Nondeterminism in Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2026.15,
  author =	{Ball, Marshall and Crawford-Kahrl, Peter},
  title =	{{How to Use Nondeterminism in Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.15},
  URN =		{urn:nbn:de:0030-drops-253024},
  doi =		{10.4230/LIPIcs.ITCS.2026.15},
  annote =	{Keywords: limited nondeterminism, cryptography, computational complexity, hardness amplification, pseudorandom generators, hardcore bits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.54
Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space

Authors: Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter ̅α. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct. For the triangle counting task, we give an algorithm that requires no promise on the input graph G, and computes a (1±ε)-approximation for the number of triangles t in G in time O^*((m⋅ α(G))/t + m/(t^{2/3)}), where α(G) is the arboricity of the graph. The algorithm can be used on any graph G (no prior knowledge of the arboricity α(G) is required), and the algorithm adapts its run-time on the fly based on the graph G. We accomplish this by trying a sequence of candidate values α̃ for α(G) and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates α̃ cannot lead to wrong estimates: if the advice is incorrect, the algorithm either succeeds despite this or detects this and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability. We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty. We further demonstrate implications of our results for triangle counting in the streaming model.
Cite as

Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan. Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 54:1-54:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ITCS.2026.54,
  author =	{Eden, Talya and Rubinfeld, Ronitt and Vasilyan, Arsen},
  title =	{{Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{54:1--54:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.54},
  URN =		{urn:nbn:de:0030-drops-253417},
  doi =		{10.4230/LIPIcs.ITCS.2026.54},
  annote =	{Keywords: Sublinear Algorithms, Triangle Counting, Edge Counting, Arboricity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.67
Query Lower Bounds for Correlation Clustering Under Memory Constraints

Authors: Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
This work initiates the study of memory–query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non‑edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of ε n², any algorithm requires Ω(n/ε²) adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make ≫ n/ε² adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.
Cite as

Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou. Query Lower Bounds for Correlation Clustering Under Memory Constraints. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2026.67,
  author =	{Garg, Sumegha and He, Songhua and Papakonstantinou, Periklis A.},
  title =	{{Query Lower Bounds for Correlation Clustering Under Memory Constraints}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{67:1--67:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.67},
  URN =		{urn:nbn:de:0030-drops-253542},
  doi =		{10.4230/LIPIcs.ITCS.2026.67},
  annote =	{Keywords: correlation clustering, query-space complexity, information theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.68
Fourier Sparsity of Delta Functions and Matching Vector PIRs

Authors: Fatemeh Ghasemi and Swastik Kopparty

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes. For integers m,r, define a delta function on {0,1}^r ⊆ ℤ_m^r to be a function f: ℤ_m^r → C if f(0) = 1 and f(x) = 0 for all nonzero Boolean x. The basic question that we study is how small can the Fourier sparsity of a delta function be; namely, how sparse can such an f be in the Fourier basis? In addition to being intrinsically interesting and natural, such questions arise naturally while studying "S-decoding polynomials" for the known matching vector families. Finding S-decoding polynomials of reduced sparsity - which corresponds to finding delta functions with low Fourier sparsity - would improve the current best PIR schemes. We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improvements to the Matching Vector PIR schemes simply by finding better S-decoding polynomials. In particular, there are no S-decoding polynomials which can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication for constantly many servers. Many interesting questions remain open.
Cite as

Fatemeh Ghasemi and Swastik Kopparty. Fourier Sparsity of Delta Functions and Matching Vector PIRs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 68:1-68:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.ITCS.2026.68,
  author =	{Ghasemi, Fatemeh and Kopparty, Swastik},
  title =	{{Fourier Sparsity of Delta Functions and Matching Vector PIRs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{68:1--68:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.68},
  URN =		{urn:nbn:de:0030-drops-253556},
  doi =		{10.4230/LIPIcs.ITCS.2026.68},
  annote =	{Keywords: Fourier Sparsity, Matching Vectors, Private Information Retrieval}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.71
Lower Bounds on FSS from Dynamic Data Structures

Authors: Niv Gilboa and Daniel Weber

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In Function Secret Sharing (FSS), a dealer with a given function f: {0,1}ⁿ → 𝔾 from n bits to a commutative group 𝔾 such that f is in a function class ℱ shares succinct keys with two properties. Evaluating each key separately on a common input x results in additive shares of f(x) and any subset of the keys does not provide information on f. Two-party FSS schemes which are reducible to One-way Functions (OWF) have applications in cryptography, complexity, and in practical data security systems. We establish a two-way transformation between a two-party FSS scheme for a function class ℱ, which is black-box reducible to an OWF, or even black-box reducible to a family of Pseudo-Random Functions (PRF) and a dynamic data structure that supports range queries on ℱ. A data structure of this type enables dynamically adding functions to a multiset of functions F ⊆ ℱ, and answering range queries on the output of F, i.e., returning ∑_{f ∈ F} f(x) for a query x. The data structures are defined in one of several models which abstract RAM. The correspondence together with known lower bounds on the update time and the query time in data structures leads to the first non-trivial lower bounds on FSS schemes which are black-box reducible to PRF. These lower bounds apply to FSS schemes with polynomial key size and include: - For ℱ^d_{box}, the class of all functions which assign a constant group element β ∈ 𝔾 to any input in a specified d-dimensional box and 0 to all other inputs: if the key sharing function, Gen, runs in time polynomial in n and the evaluation function is Eval then: - If d ≥ 2 and 𝔾 = ℤ₂ then Eval’s running time is Ω ((n^{3/2})/(log³ n)). - If d ≥ 2 and 𝔾 is cyclic such that log |𝔾| = (1 + ε) n then Eval’s running time is Ω ((n/(log n)) ²). - If d > 2 is a constant and further, Gen and Eval correspond to operations on data structures in the Oblivious Group Model (this includes all known FSS from OWF techniques), then the product of Eval’s time and the key size is Ω(n^{d-1}). - For ℱ_{mono}, the class of all monomials ax^b ∈ 𝔽_{2ⁿ}[X] such that b ≤ B, assuming n^{ω(1)} ≤ B ≤ 2^{n/4}: if Gen runs in polynomial time, then Eval’s running time is Ω ((n √{log B})/(log² n)).
Cite as

Niv Gilboa and Daniel Weber. Lower Bounds on FSS from Dynamic Data Structures. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.ITCS.2026.71,
  author =	{Gilboa, Niv and Weber, Daniel},
  title =	{{Lower Bounds on FSS from Dynamic Data Structures}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{71:1--71:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.71},
  URN =		{urn:nbn:de:0030-drops-253585},
  doi =		{10.4230/LIPIcs.ITCS.2026.71},
  annote =	{Keywords: FSS, Data Structures, Lower Bounds, Black-Box Reductions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.117
On the Power of Computationally Sound Interactive Proofs of Proximity

Authors: Hadar Strauss

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are ε-far from the property being verified, where ε > 0 is a proximity parameter. In such proof systems, the verifier has oracle access to the input, and it engages in two types of activities before making its decision: querying the input oracle and communicating with the prover. The main objective is to achieve protocols where both the query and communication complexities are extremely low. In this work, we focus on computationally sound IPPs (cs-IPPs). We study their power in two aspects: - Query complexity: We show that, assuming the existence of collision-resistant hashing functions (CRHFs), any public-coin cs-IPP that has query complexity q can be transformed into a cs-IPP that makes only O(1/ε) queries, while increasing the communication complexity by roughly q. If we further assume the existence of a good computational PIR (private information retrieval) scheme, then a similar transformation holds for general (i.e., possibly private-coin) cs-IPPs. - Coordination: Aside from the low query complexity, the resulting cs-IPP has only minimal coordination between the verifier’s two activities. The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracle. Goldreich, Rothblum, and Skverer (ITCS 2023) introduced two restricted models of IPPs that are minimally coordinated: The pre-coordinated model, where no information flows between the querying and interacting activities, but they may use a common source of randomness, and the isolated model, where the two activities are fully independent, each operating with a separate source of randomness. Our transformation shows that (under the aforementioned computational assumptions) any cs-IPP can be made to be in the pre-coordinated model, while preserving its efficiency. Hence, pre-coordinated cs-IPPs are essentially as powerful as general cs-IPPs. In contrast, we show that cs-IPPs in the isolated model are extremely limited, offering almost no advantage over property testers. Specifically, extending on a result shown by Goldreich et al. for unconditionally sound IPPs in the isolated model, we show that if a property has a cs-IPP in the isolated model that makes q queries and uses c > 0 bits of communication, then it has a tester with query complexity O(c⋅ q).
Cite as

Hadar Strauss. On the Power of Computationally Sound Interactive Proofs of Proximity. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 117:1-117:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{strauss:LIPIcs.ITCS.2026.117,
  author =	{Strauss, Hadar},
  title =	{{On the Power of Computationally Sound Interactive Proofs of Proximity}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{117:1--117:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.117},
  URN =		{urn:nbn:de:0030-drops-254047},
  doi =		{10.4230/LIPIcs.ITCS.2026.117},
  annote =	{Keywords: Interactive Proofs of Proximity, Computational Soundness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.34
Testing Classical Properties from Quantum Data

Authors: Matthias C. Caro, Preksha Naik, and Joseph Slote

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Cite as

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing Classical Properties from Quantum Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caro_et_al:LIPIcs.ITCS.2026.34,
  author =	{Caro, Matthias C. and Naik, Preksha and Slote, Joseph},
  title =	{{Testing Classical Properties from Quantum Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{34:1--34:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.34},
  URN =		{urn:nbn:de:0030-drops-253213},
  doi =		{10.4230/LIPIcs.ITCS.2026.34},
  annote =	{Keywords: Quantum Property Testing, Quantum Data, Boolean Functions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.18
Interactive Proofs for Distribution Testing with Conditional Oracles

Authors: Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompanied by notable progress (e.g., Herman and Rothblum, STOC 2022, FOCS 2023; Herman, RANDOM 2024). In this model, a data-poor verifier determines whether a probability distribution has a property of interest by interacting with an all-powerful, data-rich but untrusted prover bent on convincing them that it has the property. While prior work gave sample-, time-, and communication-efficient protocols for testing and estimating a range of distribution properties, they all suffer from an inherent issue: for most interesting properties of distributions over a domain of size N, the verifier must draw at least Ω(√N) samples of its own. While sublinear in N, this is still prohibitive for large domains encountered in practice. In this work, we circumvent this limitation by augmenting the verifier with the ability to perform an exponentially smaller number of more powerful (but reasonable) pairwise conditional queries, effectively enabling them to perform "local comparison checks" of the prover’s claims. We systematically investigate the landscape of interactive proofs in this new setting, giving poly-logarithmic query and sample protocols for (tolerantly) testing all label-invariant properties, thus demonstrating exponential savings without compromising on communication, for this large and fundamental class of testing tasks.
Cite as

Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar. Interactive Proofs for Distribution Testing with Conditional Oracles. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.ITCS.2026.18,
  author =	{Biswas, Ari and Bun, Mark and Canonne, Cl\'{e}ment L. and Sivakumar, Satchit},
  title =	{{Interactive Proofs for Distribution Testing with Conditional Oracles}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.18},
  URN =		{urn:nbn:de:0030-drops-253059},
  doi =		{10.4230/LIPIcs.ITCS.2026.18},
  annote =	{Keywords: Distribution Testing, Interactive Proofs}
}
  • Refine by Type
  • 131 Document/PDF
  • 100 Document/HTML

  • Refine by Publication Year
  • 18 2026
  • 81 2025
  • 4 2024
  • 6 2023
  • 4 2022
  • Show More...

  • Refine by Author
  • 22 Sudan, Madhu
  • 6 Guruswami, Venkatesan
  • 6 Srinivasan, Srikanth
  • 4 Amireddy, Prashanth
  • 4 Khanna, Sanjeev
  • Show More...

  • Refine by Series/Journal
  • 127 LIPIcs
  • 1 OASIcs
  • 1 LITES
  • 1 TGDK
  • 1 DagSemRep

  • Refine by Classification
  • 19 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 16 Theory of computation → Error-correcting codes
  • 13 Mathematics of computing → Coding theory
  • 12 Theory of computation → Problems, reductions and completeness
  • 11 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 6 error-correcting codes
  • 5 Property Testing
  • 4 Approximation Algorithms
  • 3 Computational Complexity
  • 3 List Decoding
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact