12 Search Results for "Dinesh, Krishnamoorthy"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

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

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3:23},
  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.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.TQC.2025.11
Quantum Catalytic Space

Authors: Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.
Cite as

Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker. Quantum Catalytic Space. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2025.11,
  author =	{Buhrman, Harry and Folkertsma, Marten and Mertz, Ian and Speelman, Florian and Strelchuk, Sergii and Subramanian, Sathyawageeswar and Tupker, Quinten},
  title =	{{Quantum Catalytic Space}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{11:1--11:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.11},
  URN =		{urn:nbn:de:0030-drops-240606},
  doi =		{10.4230/LIPIcs.TQC.2025.11},
  annote =	{Keywords: quantum computing, quantum complexity, space-bounded algorithms, catalytic computation, one clean qubit}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.6
Catalytic Computing and Register Programs Beyond Log-Depth

Authors: Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, and Antoine Vinciguerra

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In a seminal work, Buhrman et al. (STOC 2014) defined the class CSPACE(s,c) of problems solvable in space s with an additional catalytic tape of size c, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform TC¹ circuits are computable in catalytic logspace, i.e., CL = CSPACE(O(log{n}), 2^{O(log{n})}), thus giving strong evidence that catalytic space gives L strict additional power. Their study focuses on an arithmetic model called register programs, which has been a focal point in development since then. Understanding CL remains a major open problem, as TC¹ remains the most powerful containment to date. In this work, we study the power of catalytic space and register programs to compute circuits of larger depth. Using register programs, we show that for every ε > 0, SAC² ⊆ CSPACE (O((log²n)/(log log n)), 2^{O(log^{1+ε} n)}) . On the other hand, we know that SAC² ⊆ TC² ⊆ CSPACE(O(log²{n}) , 2^{O(log{n})}). Our result thus shows an O(log log n) factor improvement on the free space needed to compute SAC², at the expense of a nearly-polynomial-sized catalytic tape. We also exhibit non-trivial register programs for matrix powering, which is a further step towards showing NC² ⊆ CL.
Cite as

Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, and Antoine Vinciguerra. Catalytic Computing and Register Programs Beyond Log-Depth. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alekseev_et_al:LIPIcs.MFCS.2025.6,
  author =	{Alekseev, Yaroslav and Filmus, Yuval and Mertz, Ian and Smal, Alexander and Vinciguerra, Antoine},
  title =	{{Catalytic Computing and Register Programs Beyond Log-Depth}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.6},
  URN =		{urn:nbn:de:0030-drops-241136},
  doi =		{10.4230/LIPIcs.MFCS.2025.6},
  annote =	{Keywords: catalytic computing, circuit classes, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.29
Generalised Linial-Nisan Conjecture Is False for DNFs

Authors: Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, and Weiqiang Yuan

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexample for depth-2 circuits (DNFs). This shows, for instance, that Bazzi’s celebrated result (k-wise independence fools DNFs) cannot be generalised in a natural way. We also propose a way to circumvent our counterexample: We define a new notion of pseudorandomness called local couplings and show that it fools DNFs and even decision lists.
Cite as

Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, and Weiqiang Yuan. Generalised Linial-Nisan Conjecture Is False for DNFs. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alekseev_et_al:LIPIcs.CCC.2025.29,
  author =	{Alekseev, Yaroslav and G\"{o}\"{o}s, Mika and Guan, Ziyi and Maystre, Gilbert and Riazanov, Artur and Sokolov, Dmitry and Yuan, Weiqiang},
  title =	{{Generalised Linial-Nisan Conjecture Is False for DNFs}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.29},
  URN =		{urn:nbn:de:0030-drops-237231},
  doi =		{10.4230/LIPIcs.CCC.2025.29},
  annote =	{Keywords: pseudorandomness, DNFs, bounded independence}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.50
Fully Characterizing Lossy Catalytic Computation

Authors: Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as catalytic logspace (CL), can compute problems which are believed to be impossible for L. A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined lossy catalytic logspace (LCL[e]) as a variant of CL where we allow up to e errors when resetting the catalytic tape. They showed that LCL[e] = CL for any e = O(1), which remains the frontier of our understanding. In this work we completely characterize lossy catalytic space (LCSPACE[s,c,e]) in terms of ordinary catalytic space (CSPACE[s,c]). We show that LCSPACE[s,c,e] = CSPACE[Θ(s + e log c), Θ(c)] In other words, allowing e errors on a catalytic tape of length c is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional e log c bits of ordinary working memory. As a consequence, we show that for any e, LCL[e] = CL implies SPACE[e log n] ⊆ ZPP, thus giving a barrier to any improvement beyond LCL[O(1)] = CL. We also show equivalent results for non-deterministic and randomized catalytic space.
Cite as

Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully Characterizing Lossy Catalytic Computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{folkertsma_et_al:LIPIcs.ITCS.2025.50,
  author =	{Folkertsma, Marten and Mertz, Ian and Speelman, Florian and Tupker, Quinten},
  title =	{{Fully Characterizing Lossy Catalytic Computation}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.50},
  URN =		{urn:nbn:de:0030-drops-226786},
  doi =		{10.4230/LIPIcs.ITCS.2025.50},
  annote =	{Keywords: Space complexity, catalytic computation, error-correcting codes}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.23
Bounded Simultaneous Messages

Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Sruthi Sekar

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function f(x,y) of their inputs by sending polynomial-size messages to a computationally bounded Carol? The special case where f is the mod-2 inner-product function and Carol is bounded to AC⁰ has been studied in previous works. The general question can be broadly motivated by applications in which distributed computation is more costly than local computation. In this work, we initiate a more systematic study of the BSM model, with different functions f and computational bounds on Carol. In particular, we give evidence against the existence of BSM protocols with polynomial-size Carol for naturally distributed variants of NP-complete languages.
Cite as

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Sruthi Sekar. Bounded Simultaneous Messages. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.FSTTCS.2023.23,
  author =	{Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Sekar, Sruthi},
  title =	{{Bounded Simultaneous Messages}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-193961},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.23},
  annote =	{Keywords: Simultaneous Messages, Instance Hiding, Algebraic degree, Preprocessing, Lower Bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.43
Classical Simulation of One-Query Quantum Distinguishers

Authors: Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, and John C. S. Lui

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

Abstract
We study the relative advantage of classical and quantum distinguishers of bounded query complexity over n-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is ε-distinguishable by a one-query quantum algorithm, but O(ε k/√n)-indistinguishable by any non-adaptive k-query classical algorithm. We show that every pair of distributions that is ε-distinguishable by a one-query quantum algorithm is distinguishable with k classical queries and (1) advantage min{Ω(ε√{k/n})), Ω(ε²k²/n)} non-adaptively (i.e., in one round), and (2) advantage Ω(ε²k/√{n log n}) in two rounds. As part of our analysis, we introduce a general method for converting unbiased estimators into distinguishers.
Cite as

Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, and John C. S. Lui. Classical Simulation of One-Query Quantum Distinguishers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.APPROX/RANDOM.2023.43,
  author =	{Bogdanov, Andrej and Cheung, Tsun Ming and Dinesh, Krishnamoorthy and Lui, John C. S.},
  title =	{{Classical Simulation of One-Query Quantum Distinguishers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.43},
  URN =		{urn:nbn:de:0030-drops-188684},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.43},
  annote =	{Keywords: Query complexity, quantum algorithms, hypothesis testing, Grothendieck’s inequality}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.36
Sampling and Certifying Symmetric Functions

Authors: Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov

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

Abstract
A circuit 𝒞 samples a distribution X with an error ε if the statistical distance between the output of 𝒞 on the uniform input and X is ε. We study the hardness of sampling a uniform distribution over the set of n-bit strings of Hamming weight k denoted by Uⁿ_k for decision forests, i.e. every output bit is computed as a decision tree of the inputs. For every k there is an O(log n)-depth decision forest sampling Uⁿ_k with an inverse-polynomial error [Emanuele Viola, 2012; Czumaj, 2015]. We show that for every ε > 0 there exists τ such that for decision depth τ log (n/k) / log log (n/k), the error for sampling U_kⁿ is at least 1-ε. Our result is based on the recent robust sunflower lemma [Ryan Alweiss et al., 2021; Rao, 2019]. Our second result is about matching a set of n-bit strings with the image of a d-local circuit, i.e. such that each output bit depends on at most d input bits. We study the set of all n-bit strings whose Hamming weight is at least n/2. We improve the previously known locality lower bound from Ω(log^* n) [Beyersdorff et al., 2013] to Ω(√log n), leaving only a quartic gap from the best upper bound of O(log² n).
Cite as

Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36,
  author =	{Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry},
  title =	{{Sampling and Certifying Symmetric Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{36:1--36:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.36},
  URN =		{urn:nbn:de:0030-drops-188611},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.36},
  annote =	{Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.26
Bounded Indistinguishability for Simple Sources

Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.
Cite as

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26,
  author =	{Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram},
  title =	{{Bounded Indistinguishability for Simple Sources}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-156223},
  doi =		{10.4230/LIPIcs.ITCS.2022.26},
  annote =	{Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.31
Diameter Versus Certificate Complexity of Boolean Functions

Authors: Siddhesh Chaubal and Anna Gál

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we show that diameter is always upper bounded by certificate complexity. We argue that estimating diameter may help to get improved bounds on certificate complexity in terms of sensitivity, and other measures. Previous results due to Lin and Zhang [Krishnamoorthy Dinesh and Jayalal Sarma, 2018] imply that s(f) ≥ Ω(n^{1/3}) for transitive functions with constant alternating number. We improve and extend this bound and prove that s(f) ≥ √n for transitive functions with constant alternating number, as well as for transitive functions with constant diameter. {We also show that bs(f) ≥ Ω(n^{3/7}) for transitive functions under the weaker condition that the "minimum" diameter is constant.} Furthermore, we prove that the log-rank conjecture holds for functions of the form f(x ⊕ y) for functions f with diameter bounded above by a polynomial of the logarithm of the Fourier sparsity of the function f.
Cite as

Siddhesh Chaubal and Anna Gál. Diameter Versus Certificate Complexity of Boolean Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chaubal_et_al:LIPIcs.MFCS.2021.31,
  author =	{Chaubal, Siddhesh and G\'{a}l, Anna},
  title =	{{Diameter Versus Certificate Complexity of Boolean Functions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-144713},
  doi =		{10.4230/LIPIcs.MFCS.2021.31},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Certificate Complexity, Block Sensitivity, Log-rank Conjecture, Alternating Number}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.17
Limits of Preprocessing

Authors: Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
It is a classical result that the inner product function cannot be computed by an AC⁰ circuit [Merrick L. Furst et al., 1981; Miklós Ajtai, 1983; Johan Håstad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{ω(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning AC⁰ under simple input distributions.
Cite as

Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler. Limits of Preprocessing. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.CCC.2020.17,
  author =	{Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Kindler, Guy},
  title =	{{Limits of Preprocessing}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  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.CCC.2020.17},
  URN =		{urn:nbn:de:0030-drops-125697},
  doi =		{10.4230/LIPIcs.CCC.2020.17},
  annote =	{Keywords: circuit, communication complexity, IPPP, preprocessing, PRF, simultaneous messages}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.37
Characterization and Lower Bounds for Branching Program Size Using Projective Dimension

Authors: Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We study projective dimension, a graph parameter (denoted by pd(G) for a graph G), introduced by Pudlak and Rodl (1992). For a Boolean function f(on n bits), Pudlak and Rodl associated a bipartite graph G_f and showed that size of the optimal branching program computing f (denoted by bpsize(f)) is at least pd(G_f) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) imply lower bounds for bpsize(f). Despite several attempts (Pudlak and Rodl (1992), Ronyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f) is 2^{Omega(n)}. Motivated by the argument in Pudlak and Rodl (1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd(f)) and {bitwise decomposable projective dimension} (denoted by bpdim(f)). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2^{Omega(n)}. In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a large constant c>0 and for any function f, bpdim(f)/6 <= bpsize(f) <= (bpdim(f))^c. (b) We introduce a new candidate function family f for showing super-polynomial lower bounds for bpdim(f). As our main result, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(sqrt{n}), upd(f) = Omega(n), bpdim(f) = Omega({n^{1.5}}/{log(n)}). (c) Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.
Cite as

Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma. Characterization and Lower Bounds for Branching Program Size Using Projective Dimension. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dinesh_et_al:LIPIcs.FSTTCS.2016.37,
  author =	{Dinesh, Krishnamoorthy and Koroth, Sajin and Sarma, Jayalal},
  title =	{{Characterization and Lower Bounds for Branching Program Size Using Projective Dimension}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.37},
  URN =		{urn:nbn:de:0030-drops-68722},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.37},
  annote =	{Keywords: Projective Dimension, Lower Bounds, Branching Program Size}
}
  • Refine by Type
  • 12 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 3 2023
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 5 Filmus, Yuval
  • 4 Dinesh, Krishnamoorthy
  • 3 Alekseev, Yaroslav
  • 3 Bogdanov, Andrej
  • 3 Ishai, Yuval
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Circuit complexity
  • 5 Theory of computation → Complexity classes
  • 4 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Probabilistic computation
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 2 Lower Bounds
  • 2 catalytic computation
  • 1 Algebraic degree
  • 1 Algorithms
  • 1 Alternating Number
  • 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