50 Search Results for "Kopparty, Swastik"

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.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.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.90
Slice Rank and Partition Rank of the Determinant

Authors: Amichai Lampert and Guy Moshkovitz

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

Abstract
The Laplace expansion expresses the n × n determinant det_n as a sum of n products. Do shorter expansions exist? In this paper we: - Fully determine the slice rank decompositions of det_n (where each product must contain a linear factor): In this case, we show that n summands are necessary, and moreover, the only such expansions with n summands are equivalent (in a precise sense) to the Laplace expansion. - Prove a logarithmic lower bound for the partition rank of det_n (where each product is of multilinear forms): In this case, we show that at least log₂(n)+1 summands are needed and we explain why existing techniques fail to yield any nontrivial lower bound. - Separate partition rank from slice rank for det_n: we find a quadratic expansion for det₄, over any field, with fewer summands than the Laplace expansion. This construction is related to a well-known example of Green-Tao and Lovett-Meshulam-Samorodnitsky disproving the naive version of the Gowers Inverse conjecture over small fields. An important motivation for these questions comes from the challenge of separating structure and randomness for tensors. On the one hand, we show that the random construction fails to separate: for a random tensor of partition rank r, the analytic rank is r-o(1) with high probability. On the other hand, our results imply that the determinant yields the first asymptotic separation between partition rank and analytic rank of d-tensors, with their ratio tending to infinity with d.
Cite as

Amichai Lampert and Guy Moshkovitz. Slice Rank and Partition Rank of the Determinant. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lampert_et_al:LIPIcs.ITCS.2026.90,
  author =	{Lampert, Amichai and Moshkovitz, Guy},
  title =	{{Slice Rank and Partition Rank of the Determinant}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{90:1--90:15},
  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.90},
  URN =		{urn:nbn:de:0030-drops-253779},
  doi =		{10.4230/LIPIcs.ITCS.2026.90},
  annote =	{Keywords: Slice rank, partition rank, determinant}
}
Document
DOI: 10.4230/DagRep.15.3.56
Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111)

Authors: Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, and Ian Mertz

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract
This report documents the program and activities of Dagstuhl Seminar 25111 "Computational Complexity of Discrete Problems," which was held during March 09-14, 2025. The seminar brought together researchers working in many diverse sub-areas of computational complexity, promoting a vibrant exchange of ideas. Following a description of the seminar’s objectives and its overall organization, this report lists the different major talks given during the seminar in alphabetical order of speakers, followed by the abstracts of the talks, including the main references and relevant sources where applicable.
Cite as

Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, and Ian Mertz. Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111). In Dagstuhl Reports, Volume 15, Issue 3, pp. 56-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{kopparty_et_al:DagRep.15.3.56,
  author =	{Kopparty, Swastik and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Mertz, Ian},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111)}},
  pages =	{56--76},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Kopparty, Swastik and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Mertz, Ian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.56},
  URN =		{urn:nbn:de:0030-drops-249007},
  doi =		{10.4230/DagRep.15.3.56},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.37
Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields

Authors: Fatemeh Ghasemi, Gal Gross, and Swastik Kopparty

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
This paper is motivated by basic complexity and probability questions about permanents of random matrices over small finite fields, and in particular, about properties separating the permanent and the determinant. Let q be a fixed odd prime, and let k ≤ n both be growing. For a uniformly random n × k matrix A over 𝔽_q, we study the probability that all k × k submatrices of A have zero permanent; namely that A does not have full permanental rank. When k = n, this is simply the probability that a random square matrix over 𝔽_q has zero permanent, which we do not understand. We believe that the probability in this case is 1/q + o(1), which would be in contrast to the case of the determinant, where the answer is 1/q + Ω_q(1). Our main result is that when k is O(√n), the probability that a random n × k matrix does not have full permanental rank is essentially the same as the probability that the matrix has a 0 column, namely (1 +o(1)) k/qⁿ. In contrast, for determinantal (standard) rank the analogous probability is Θ(q^k/q^n). At the core of our result are some basic linear algebraic properties of the permanent that distinguish it from the determinant.
Cite as

Fatemeh Ghasemi, Gal Gross, and Swastik Kopparty. Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.APPROX/RANDOM.2025.37,
  author =	{Ghasemi, Fatemeh and Gross, Gal and Kopparty, Swastik},
  title =	{{Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.37},
  URN =		{urn:nbn:de:0030-drops-244037},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.37},
  annote =	{Keywords: Permanent, random matrices over a finite field}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.34
Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) is invariant under simultaneous permutations of the coordinates of u and v.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost 𝒪(1)-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid 𝒮ⁿ to an Abelian group, correcting from a near-optimal (1/|𝒮|^d - ε) fraction of errors for every ε > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2025.34,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  URN =		{urn:nbn:de:0030-drops-244004},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  annote =	{Keywords: Markov Chains, Random Walk, Multislices, Representation Theory of Symmetric Group, Local Correction, Low-degree Polynomials, Polynomial Distance Lemma}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.36
Simplifying Armoni’s PRG

Authors: Ben Chen and Amnon Ta-Shma

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni’s PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be obtained as simple variants of INW. For the construction to work we need space-efficient extractors with tiny entropy loss. We use the extractors from [Chattopadhyay and Liao, 2020] instead of [Guruswami et al., 2009] taking advantage of the very high min-entropy regime we work with. We remark that using these extractors has the additional benefit of making the dependence on the branching program alphabet Σ correct.
Cite as

Ben Chen and Amnon Ta-Shma. Simplifying Armoni’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 36:1-36:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.36,
  author =	{Chen, Ben and Ta-Shma, Amnon},
  title =	{{Simplifying Armoni’s PRG}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{36:1--36:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  URN =		{urn:nbn:de:0030-drops-244024},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  annote =	{Keywords: PRG, ROBP, read-once, random, psuedorandom, armoni, derandomization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.29
A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms

Authors: Igor Shinkar and Harsimran Singh

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of transforming an algorithm for matrix multiplication, whose output has a small fraction of the entries correct into a matrix multiplication algorithm, whose output is fully correct for all inputs. In this work, we provide a new and simple way to transform an average-case algorithm that takes two matrices A,B ∈ 𝔽_p^{n×n} for a prime p, and outputs a matrix that agrees with the matrix product AB on a 1/p + ε fraction of entries on average for a small ε > 0, into a worst-case algorithm that correctly computes the matrix product for all possible inputs. Our reduction employs list-decodable codes to transform an average-case algorithm into an algorithm with one-sided error, which are known to admit efficient reductions from the work of Gola, Shinkar, and Singh [Gola et al., 2024]. Our reduction is more concise and straightforward compared to the recent work of Hirahara and Shimizu [Hirahara and Shimizu, 2025], and improves the overhead in the running time incurred during the reduction.
Cite as

Igor Shinkar and Harsimran Singh. A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shinkar_et_al:LIPIcs.APPROX/RANDOM.2025.29,
  author =	{Shinkar, Igor and Singh, Harsimran},
  title =	{{A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.29},
  URN =		{urn:nbn:de:0030-drops-243953},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.29},
  annote =	{Keywords: Matrix Multiplication, Reductions, Worst case to average case reductions}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.66
Testing Isomorphism of Boolean Functions over Finite Abelian Groups

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

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Let f and g be Boolean functions over a finite Abelian group 𝒢, where g is fully known and f is accessible via queries; that is, given any x ∈ 𝒢, we can obtain the value f(x). We study the problem of tolerant isomorphism testing: given parameters ε ≥ 0 and τ > 0, the goal is to determine, using as few queries as possible, whether there exists an automorphism σ of 𝒢 such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for every automorphism σ, the distance is at least ε + τ. We design an efficient tolerant property testing algorithm for this problem over finite Abelian groups with constant exponent. The exponent of a finite group refers to the largest order of any element in the group. The query complexity of our algorithm is polynomial in s and 1/τ, where s bounds the spectral norm of the function g, and τ is the tolerance parameter. In addition, we present an improved algorithm in the case where g is Fourier sparse, meaning that its Fourier expansion contains only a small number of nonzero coefficients. Our approach draws on key ideas from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner product defined over finite Abelian groups. We believe that these techniques will be useful more broadly in the design of property testing algorithms.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Testing Isomorphism of Boolean Functions over Finite Abelian Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.APPROX/RANDOM.2025.66,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Testing Isomorphism of Boolean Functions over Finite Abelian Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{66:1--66:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  URN =		{urn:nbn:de:0030-drops-244328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  annote =	{Keywords: Analysis of Boolean functions, Abelian groups, Automorphism group, Function isomorphism, Spectral norm}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.57
List-Recovery of Random Linear Codes over Small Fields

Authors: Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate ε-close to capacity, and aim to bound the dependence of the output list size L on ε, the input list size 𝓁, and the alphabet size q. Prior to our work, the best upper bound was L = q^O(𝓁/ε) (Zyablov and Pinsker, Prob. Per. Inf. 1981). Previous work has identified cases in which linear codes provably perform worse than non-linear codes with respect to list-recovery. While there exist non-linear codes that achieve L = O(𝓁/ε), we know that L ≥ 𝓁^Ω(1/ε) is necessary for list recovery from erasures over fields of small characteristic, and for list recovery from errors over large alphabets. We show that in other relevant regimes there is no significant price to pay for linearity, in the sense that we get the correct dependence on the gap-to-capacity ε and go beyond the Zyablov-Pinsker bound for the first time. Specifically, when q is constant and ε approaches zero, - For list-recovery from erasures over prime fields, we show that L ≤ C₁/ε. By prior work, such a result cannot be obtained for low-characteristic fields. - For list-recovery from errors over arbitrary fields, we prove that L ≤ C₂/ε. Above, C₁ and C₂ depend on the decoding radius, input list size, and field size. We provide concrete bounds on the constants above, and the upper bounds on L improve upon the Zyablov-Pinsker bound whenever q ≤ 2^{(1/ε)^c} for some small universal constant c > 0.
Cite as

Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro. List-Recovery of Random Linear Codes over Small Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.57,
  author =	{Doron, Dean and Mosheiff, Jonathan and Resch, Nicolas and Ribeiro, Jo\~{a}o},
  title =	{{List-Recovery of Random Linear Codes over Small Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.57},
  URN =		{urn:nbn:de:0030-drops-244239},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.57},
  annote =	{Keywords: List recovery, random linear codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.53
Near-Optimal List-Recovery of Linear Code Families

Authors: Ray Li and Nikhil Shagrithaya

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independent of the alphabet size and length). That is, over alphabets of size at least 𝓁^Ω(1/ε), random linear codes of rate R are (1-R-ε, 𝓁, (𝓁/ε)^O(𝓁/ε))-list-recoverable for all R ∈ (0,1) and 𝓁. Together with a result of Levi, Mosheiff, and Shagrithaya, this implies that randomly punctured Reed-Solomon codes also achieve list-recovery capacity. We also prove that our output list size is near-optimal among all linear codes: all (1-R-ε, 𝓁, L)-list-recoverable linear codes must have L ≥ 𝓁^{Ω(R/ε)}. Our simple upper bound combines the Zyablov-Pinsker argument with recent bounds from Kopparty, Ron-Zewi, Saraf, Wootters, and Tamo on the maximum intersection of a "list-recovery ball" and a low-dimensional subspace with large distance. Our lower bound is inspired by a recent lower bound of Chen and Zhang.
Cite as

Ray Li and Nikhil Shagrithaya. Near-Optimal List-Recovery of Linear Code Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2025.53,
  author =	{Li, Ray and Shagrithaya, Nikhil},
  title =	{{Near-Optimal List-Recovery of Linear Code Families}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  URN =		{urn:nbn:de:0030-drops-244199},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  annote =	{Keywords: Error-Correcting Codes, Randomness, List-Recovery, Reed-Solomon Codes, Random Linear Codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.59
Testing Tensor Products of Algebraic Codes

Authors: Sumegha Garg, Madhu Sudan, and Gabriel Wu

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of (an abstraction of) algebraic geometry codes. Such codes are parameterized by, in addition to standard parameters such as block length n and dimension k, their genus g. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided n = Ω((k+g)²). Apart from Reed-Solomon codes, this seems to be the first explicit family of two-wise tensor codes of high dual distance that is robustly locally testable by the natural test that measures the expected distance of a random row/column from the underlying code.
Cite as

Sumegha Garg, Madhu Sudan, and Gabriel Wu. Testing Tensor Products of Algebraic Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX/RANDOM.2025.59,
  author =	{Garg, Sumegha and Sudan, Madhu and Wu, Gabriel},
  title =	{{Testing Tensor Products of Algebraic Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  URN =		{urn:nbn:de:0030-drops-244254},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  annote =	{Keywords: Algebraic geometry codes, Robust testability, Tensor products of codes}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.5
Information-Theoretic Random-Index PIR

Authors: Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).
Cite as

Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov. Information-Theoretic Random-Index PIR. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kolby_et_al:LIPIcs.ITC.2025.5,
  author =	{Kolby, Sebastian and Roy, Lawrence and Sternad, Jure and Yakoubov, Sophia},
  title =	{{Information-Theoretic Random-Index PIR}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.5},
  URN =		{urn:nbn:de:0030-drops-243559},
  doi =		{10.4230/LIPIcs.ITC.2025.5},
  annote =	{Keywords: Private information retrieval, Multi-server, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.8
On the Definition of Malicious Private Information Retrieval

Authors: Bar Alon and Amos Beimel

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
A multi-server private information retrieval (PIR) protocol allows a client to obtain an entry of its choice from a database, held by one or more servers, while hiding the identity of the entry from small enough coalitions of servers. In this paper, we study PIR protocols in which some of the servers are malicious and may not send messages according to the pre-described protocol. In previous papers, such protocols were defined by requiring that they are correct, private, and robust to malicious servers, i.e., by listing 3 properties that they should satisfy. However, 40 years of experience in studying secure multiparty protocols taught us that defining the security of protocols by a list of required properties is problematic. In this paper, we rectify this situation and define the security of PIR protocols with malicious servers using the real vs. ideal paradigm. We study the relationship between the property-based definition of PIR protocols and the real vs. ideal definition, showing the following results: - We prove that if we require full security from PIR protocols, e.g., the client outputs the correct value of the database entry with high probability even if a minority of the servers are malicious, then the two definitions are equivalent. This implies that constructions of such protocols that were proven secure using the property-based definition are actually secure under the "correct" definition of security. - We show that if we require security-with-abort from PIR protocols (called PIR protocols with error-detection in previous papers), i.e., protocols in which the user either outputs the correct value or an abort symbol, then there are protocols that are secure under the property-based definition; however, they do not satisfy the real vs. ideal definition, that is, they can be attacked allowing selective abort. This shows that the property-based definition of PIR protocols with security-with-abort is problematic. - We consider the compiler of Eriguchi et al. (TCC 22) that starts with a PIR protocol that is secure against semi-honest servers and constructs a PIR protocol with security-with-abort; this compiler implies the best-known PIR protocols with security-with-abort. We show that applying this compiler does not result in PIR protocols that are secure according to the real vs. ideal definition. However, we prove that a simple modification of this compiler results in PIR protocols that are secure according to the real vs. ideal definition.
Cite as

Bar Alon and Amos Beimel. On the Definition of Malicious Private Information Retrieval. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.ITC.2025.8,
  author =	{Alon, Bar and Beimel, Amos},
  title =	{{On the Definition of Malicious Private Information Retrieval}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.8},
  URN =		{urn:nbn:de:0030-drops-243581},
  doi =		{10.4230/LIPIcs.ITC.2025.8},
  annote =	{Keywords: Private information retrieval, secure multiparty computation}
}
  • Refine by Type
  • 50 Document/PDF
  • 31 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 28 2025
  • 1 2024
  • 2 2023
  • 5 2022
  • Show More...

  • Refine by Author
  • 13 Kopparty, Swastik
  • 4 Saraf, Shubhangi
  • 4 Srinivasan, Srikanth
  • 3 Potukuchi, Aditya
  • 3 Sudan, Madhu
  • Show More...

  • Refine by Series/Journal
  • 49 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 9 Mathematics of computing → Coding theory
  • 9 Theory of computation → Error-correcting codes
  • 7 Theory of computation → Algebraic complexity theory
  • 6 Theory of computation → Pseudorandomness and derandomization
  • 4 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 3 Reed-Solomon codes
  • 3 error-correcting codes
  • 2 Boolean Functions
  • 2 Coding theory
  • 2 List recovery
  • 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