32 Search Results for "De, Anindya"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.73
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu

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

Abstract
We construct a family of distributions {𝒟_n}_n with 𝒟_n over {0, 1}ⁿ and a family of depth-7 quantum circuits {C_n}_n such that 𝒟_n is produced exactly by C_n with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance 1 - e^{-Ω(n)} from 𝒟_n. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems.
Cite as

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.ITCS.2026.73,
  author =	{Grier, Daniel and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony and Wu, Kewen},
  title =	{{Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{73:1--73:14},
  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.73},
  URN =		{urn:nbn:de:0030-drops-253607},
  doi =		{10.4230/LIPIcs.ITCS.2026.73},
  annote =	{Keywords: Shallow circuits, sampling, quantum circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.70
Unconditional Pseudorandomness Against Shallow Quantum Circuits

Authors: Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan

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

Abstract
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: - Any quantum state 2-design yields unconditional pseudorandomness against both QNC⁰ circuits with arbitrarily many ancillae and AC⁰∘QNC⁰ circuits with nearly linear ancillae. - Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. - Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local QNC⁰ adversaries, even with limited AC⁰ postprocessing. Our results stand in stark contrast to the standard guarantee of the 2-design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.
Cite as

Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan. Unconditional Pseudorandomness Against Shallow Quantum Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 70:1-70:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ITCS.2026.70,
  author =	{Ghosh, Soumik and Subramanian, Sathyawageeswar and Zhan, Wei},
  title =	{{Unconditional Pseudorandomness Against Shallow Quantum Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{70:1--70:25},
  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.70},
  URN =		{urn:nbn:de:0030-drops-253578},
  doi =		{10.4230/LIPIcs.ITCS.2026.70},
  annote =	{Keywords: quantum pseudorandomness, shallow quantum circuits, pseudorandomness, t-designs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.116
Decentralized Data Archival: New Definitions and Constructions

Authors: Elaine Shi, Rose Silver, and Changrui Mu

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

Abstract
We initiate the study of a new abstraction called incremental decentralized data archival (iDDA). Specifically, imagine that there is an ever-growing, massive database such as a blockchain, a comprehensive human knowledge base like Wikipedia, or the Internet archive. We want to build a decentralized archival system for such datasets to ensure long-term robustness and sustainability. We identify several important properties that an iDDA scheme should satisfy. First, to promote heterogeneity and decentralization, we want to encourage even weak nodes with limited space (e.g., users' home computers) to contribute. The minimum space requirement to contribute should be approximately independent of the data size. Second, if a collection of nodes together receive rewards commensurate with contributing a total of m blocks of space, then we want the following reassurances: 1) if m is at least the database size, we should be able to reconstruct the entire dataset; and 2) these nodes should actually be committing roughly m space in aggregate - specifically, when m is much larger than the data size, these nodes cannot store only one copy of the database, and be able to impersonate arbitrarily many pseudonyms and get unbounded rewards. We propose new definitions that mathematically formalize the aforementioned requirements of an iDDA scheme. We also devise an efficient construction in the random oracle model which satisfies the desired security requirements. Our scheme incurs only Õ(1) audit cost, as well as Õ(1) update cost for both the publisher and each node, where Õ(⋅) hides polylogarithmic factors. Further, the minimum space provisioning required to contribute is as small as polylogarithmic. Our construction exposes several interesting technical challenges. Specifically, we show that a straightforward application of the standard hierarchical data structure fails, since both our security definition and the underlying cryptographic primitives we employ lack the desired compositional guarantees. We devise novel techniques to overcome these compositional issues, resulting in a construction with provable security while still retaining efficiency. Finally, our new definitions also make a conceptual contribution, and lay the theoretical groundwork for the study of iDDA. We raise several interesting open problems along this direction.
Cite as

Elaine Shi, Rose Silver, and Changrui Mu. Decentralized Data Archival: New Definitions and Constructions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 116:1-116:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.ITCS.2026.116,
  author =	{Shi, Elaine and Silver, Rose and Mu, Changrui},
  title =	{{Decentralized Data Archival: New Definitions and Constructions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{116:1--116: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.116},
  URN =		{urn:nbn:de:0030-drops-254037},
  doi =		{10.4230/LIPIcs.ITCS.2026.116},
  annote =	{Keywords: Decentralized Data Archival}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.30
New Bounds for Circular Trace Reconstruction

Authors: Arnav Burudgunte, Paul Valiant, and Hongao Wang

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

Abstract
The "trace reconstruction" problem asks, given an unknown binary string x and a channel that repeatedly returns "traces" of x with each bit randomly deleted with some probability p, how many traces are needed to recover x? There is an exponential gap between the best known upper and lower bounds for this problem. Many variants of the model have been introduced in hopes of motivating or revealing new approaches to narrow this gap. We study the variant of circular trace reconstruction introduced by Narayanan and Ren (ITCS 2021), in which traces undergo a random cyclic shift in addition to random deletions. We show an improved lower bound of Ω̃(n⁵) for circular trace reconstruction. This contrasts with the (previously) best known lower bounds of Ω̃(n³) in the circular case and Ω̃(n^{3/2}) in the linear case. Our bound shows the indistinguishability of traces from two sparse strings x,y that each have a constant number of nonzeros. Can this technique be extended significantly? How hard is it to reconstruct a sparse string x under a cyclic deletion channel? We resolve these questions by showing, using Fourier techniques, that Õ(n⁶) traces suffice for reconstructing any constant-sparse string in a circular deletion channel, in contrast to the best known upper bound of exp(Õ(n^{1/3})) for general strings in the circular deletion channel. This shows that new algorithms or new lower bounds must focus on non-constant-sparse strings.
Cite as

Arnav Burudgunte, Paul Valiant, and Hongao Wang. New Bounds for Circular Trace Reconstruction. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{burudgunte_et_al:LIPIcs.ITCS.2026.30,
  author =	{Burudgunte, Arnav and Valiant, Paul and Wang, Hongao},
  title =	{{New Bounds for Circular Trace Reconstruction}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{30:1--30: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.30},
  URN =		{urn:nbn:de:0030-drops-253176},
  doi =		{10.4230/LIPIcs.ITCS.2026.30},
  annote =	{Keywords: Trace reconstruction, algorithmic statistics, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.14
Testing Sumsets Is Hard

Authors: Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.
Cite as

Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir. Testing Sumsets Is Hard. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2025.14,
  author =	{Chen, Xi and Nadimpalli, Shivam and Randolph, Tim and Servedio, Rocco A. and Zamir, Or},
  title =	{{Testing Sumsets Is Hard}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.14},
  URN =		{urn:nbn:de:0030-drops-244822},
  doi =		{10.4230/LIPIcs.ESA.2025.14},
  annote =	{Keywords: Sumsets, additive combinatorics, property testing, Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.91
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.
Cite as

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dhulipala_et_al:LIPIcs.ESA.2025.91,
  author =	{Dhulipala, Laxman and Henzinger, Monika and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi},
  title =	{{Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{91:1--91:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.91},
  URN =		{urn:nbn:de:0030-drops-245601},
  doi =		{10.4230/LIPIcs.ESA.2025.91},
  annote =	{Keywords: differential privacy, abovethreshold, densest subgraph}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.40
Sublinear Space Graph Algorithms in the Continual Release Model

Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou

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

Abstract
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [Hendrik Fichtenberger et al., 2021; Shuang Song et al., 2018]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release k-core decomposition algorithm. We also develop a novel sparse level data structure for k-core decomposition that may be of independent interest. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.
Cite as

Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou. Sublinear Space Graph Algorithms in the Continual Release Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 40:1-40:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epasto_et_al:LIPIcs.APPROX/RANDOM.2025.40,
  author =	{Epasto, Alessandro and Liu, Quanquan C. and Mukherjee, Tamalika and Zhou, Felix},
  title =	{{Sublinear Space Graph Algorithms in the Continual Release Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{40:1--40:27},
  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.40},
  URN =		{urn:nbn:de:0030-drops-244064},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  annote =	{Keywords: Differential Privacy, Continual Release, Densest Subgraph, k-Core Decomposition, Maximum Matching}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.28
Implications of Better PRGs for Permutation Branching Programs

Authors: Dean Doron and William M. Hoza

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

Abstract
We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let c ∈ [1, 2) be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-6 length-n permutation ROBPs with error 1/n and seed length Õ(log^c n), then there are explicit hitting set generators (HSGs) for width-4 length-n ROBPs with threshold 1/polylog(n) and seed length Õ(log^c n). For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error ε and seed length O(log(n)⋅log(1/ε)) (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When ε = 1/n, there are known constructions of weighted pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length Õ(log^{3/2} n) (Pyne and Vadhan CCC 2021; Chen, Hoza, Lyu, Tal, and Wu FOCS 2023; Chattopadhyay and Liao ITCS 2024), but unweighted PRGs with seed length o(log² n) remain elusive. Meanwhile, for width-4 ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length o(log²n). Our reduction can be divided into two parts. First, we show that explicit low-error PRGs for width-6 permutation ROBPs with seed length Õ(log^c n) would imply explicit low-error PRGs for width-3 ROBPs with seed length Õ(log^c n). This would improve Meka, Reingold, and Tal’s PRG (STOC 2019), which has seed length o(log²n) only when the error parameter is relatively large. Second, we show that for any w, n, s, and ε, an explicit PRG for width-w ROBPs with error 0.01/n and seed length s would imply an explicit ε-HSG for width-(w + 1) ROBPs with seed length O(s + log(n)⋅log(1/ε)).
Cite as

Dean Doron and William M. Hoza. Implications of Better PRGs for Permutation Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.28,
  author =	{Doron, Dean and Hoza, William M.},
  title =	{{Implications of Better PRGs for Permutation Branching Programs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{28:1--28:20},
  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.28},
  URN =		{urn:nbn:de:0030-drops-243946},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.28},
  annote =	{Keywords: hitting set generators, pseudorandom generators, read-once branching programs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.67
On Sums of INW Pseudorandom Generators

Authors: William M. Hoza and Zelin Lv

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

Abstract
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let X be the n-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter λ. We prove that the bitwise XOR of t independent copies of X fools width-w programs with error n^{log(w + 1)} ⋅ (λ⋅log n)^t. Notably, this error bound is meaningful even for relatively large values of λ such as λ = 1/O(log n). Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs - it just gives a new way of re-proving the well-known O(log² n) bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our "XOR of INW" approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-3 programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably Ω(log² n). Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on t correlated seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
Cite as

William M. Hoza and Zelin Lv. On Sums of INW Pseudorandom Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.67,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{On Sums of INW Pseudorandom Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{67:1--67:24},
  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.67},
  URN =		{urn:nbn:de:0030-drops-244330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.67},
  annote =	{Keywords: INW generator, pseudorandomness, space-bounded computation, XOR Lemmas}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.49
Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Authors: Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy

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

Abstract
A long line of work has studied the pseudorandomness properties of walks on expander graphs. A central goal is to measure how closely the distribution over n-length walks on an expander approximates the uniform distribution of n-independent elements. One approach to do so is to label the vertices of an expander with elements from an alphabet Σ, and study closeness of the mean of functions over Σⁿ, under these two distributions. We say expander walks ε-fool a function if the expander walk mean is ε-close to the true mean. There has been a sequence of works studying this question for various functions, such as the XOR function, the AND function, etc. We show that: - The class of symmetric functions is O(|Σ|λ)-fooled by expander walks over any generic λ-expander, and any alphabet Σ . This generalizes the result of Cohen, Peri, Ta-Shma [STOC'21] which analyzes it for |Σ| = 2, and exponentially improves the previous bound of O(|Σ|^O(|Σ|) λ), by Golowich and Vadhan [CCC'22]. Moreover, if the expander is a Cayley graph over ℤ_|Σ|, we get a further improved bound of O(√{|Σ|} λ). Morever, when Σ is a finite group G, we show the following for functions over Gⁿ: - The class of symmetric class functions is O({√|G|}/D λ}-fooled by expander walks over "structured" λ-expanders, if G is D-quasirandom. - We show a lower bound of Ω(λ) for symmetric functions for any finite group G (even for "structured" λ-expanders). - We study the Fourier spectrum of a class of non-symmetric functions arising from word maps, and show that they are exponentially fooled by expander walks. Our proof employs Fourier analysis over general groups, which contrasts with earlier works that have studied either the case of ℤ₂ or ℤ. This enables us to get quantitatively better bounds even for unstructured sets.
Cite as

Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy. Pseudorandomness of Expander Walks via Fourier Analysis on Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeronimo_et_al:LIPIcs.APPROX/RANDOM.2025.49,
  author =	{Jeronimo, Fernando Granha and Mittal, Tushant and Roy, Sourya},
  title =	{{Pseudorandomness of Expander Walks via Fourier Analysis on Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{49:1--49: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.49},
  URN =		{urn:nbn:de:0030-drops-244157},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.49},
  annote =	{Keywords: Expander graphs, pseudorandomness}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.4
Time-Space Tradeoffs of Truncation with Preprocessing

Authors: Krzysztof Pietrzak and Pengxiang Wang

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

Abstract
Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected 2^k different inputs one will find an output that starts with k zeros. Using such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi et al., 2022] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for "trivial" reasons. Concretely, it’s known that any algorithm that inverts a random function or permutation with range N making T queries and using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges, which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query. We show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog N lower bound applies.
Cite as

Krzysztof Pietrzak and Pengxiang Wang. Time-Space Tradeoffs of Truncation with Preprocessing. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pietrzak_et_al:LIPIcs.ITC.2025.4,
  author =	{Pietrzak, Krzysztof and Wang, Pengxiang},
  title =	{{Time-Space Tradeoffs of Truncation with Preprocessing}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{4:1--4:10},
  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.4},
  URN =		{urn:nbn:de:0030-drops-243544},
  doi =		{10.4230/LIPIcs.ITC.2025.4},
  annote =	{Keywords: Time-Space Lower Bounds, Blockchains}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2025.34
New Fault Domains for Conformance Testing of Finite State Machines

Authors: Frits Vaandrager and Ivo Melse

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
A fault domain reflects a tester’s assumptions about faults that may occur in an implementation and that need to be detected during testing. A fault domain that has been widely studied in the literature on black-box conformance testing is the class of finite state machines (FSMs) with at most m states. Numerous strategies for generating test suites have been proposed that guarantee fault coverage for this class. These so-called m-complete test suites grow exponentially in m-n, where n is the number of states of the specification, so one can only run them for small values of m-n. But the assumption that m-n is small is not realistic in practice. In his seminal paper from 1964, Hennie raised the challenge to design checking experiments in which the number of states may increase appreciably. In order to solve this long-standing open problem, we propose (much larger) fault domains that capture the assumption that all states in an implementation can be reached by first performing a sequence from some set A (typically a state cover for the specification), followed by k arbitrary inputs, for some small k. The number of states of FSMs in these fault domains grows exponentially in k. We present a sufficient condition for k-A-completeness of test suites with respect to these fault domains. Our condition implies k-A-completeness of two prominent m-complete test suite generation strategies, the Wp and HSI methods. Thus these strategies are complete for much larger fault domains than those for which they were originally designed, and thereby solve Hennie’s challenge. We show that three other prominent m-complete methods (H, SPY and SPYH) do not always generate k-A-complete test suites.
Cite as

Frits Vaandrager and Ivo Melse. New Fault Domains for Conformance Testing of Finite State Machines. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vaandrager_et_al:LIPIcs.CONCUR.2025.34,
  author =	{Vaandrager, Frits and Melse, Ivo},
  title =	{{New Fault Domains for Conformance Testing of Finite State Machines}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{34:1--34:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.34},
  URN =		{urn:nbn:de:0030-drops-239843},
  doi =		{10.4230/LIPIcs.CONCUR.2025.34},
  annote =	{Keywords: conformance testing, finite state machines, Mealy machines, apartness, observation tree, fault domains, k-A-complete test suites}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.52
Relative-Error Testing of Conjunctions and Decision Lists

Authors: Xi Chen, William Pires, Toniann Pitassi, and Rocco A. Servedio

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the relative-error property testing model for Boolean functions that was recently introduced in the work of [X. Chen et al., 2025]. In relative-error testing, the testing algorithm gets uniform random satisfying assignments as well as black-box queries to f, and it must accept f with high probability whenever f has the property that is being tested and reject any f that is relative-error far from having the property. Here the relative-error distance from f to a function g is measured with respect to |f^{-1}(1)| rather than with respect to the entire domain size 2ⁿ as in the Hamming distance measure that is used in the standard model; thus, unlike the standard model, relative-error testing allows us to study the testability of sparse Boolean functions that have few satisfying assignments. It was shown in [X. Chen et al., 2025] that relative-error testing is at least as difficult as standard-model property testing, but for many natural and important Boolean function classes the precise relationship between the two notions is unknown. In this paper we consider the well-studied and fundamental properties of being a conjunction and being a decision list. In the relative-error setting, we give an efficient one-sided error tester for conjunctions with running time and query complexity O(1/ε). Secondly, we give a two-sided relative-error Õ(1/ε) tester for decision lists, matching the query complexity of the state-of-the-art algorithm in the standard model [Nader H. Bshouty, 2020; I. Diakonikolas et al., 2007].
Cite as

Xi Chen, William Pires, Toniann Pitassi, and Rocco A. Servedio. Relative-Error Testing of Conjunctions and Decision Lists. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.52,
  author =	{Chen, Xi and Pires, William and Pitassi, Toniann and Servedio, Rocco A.},
  title =	{{Relative-Error Testing of Conjunctions and Decision Lists}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.52},
  URN =		{urn:nbn:de:0030-drops-234291},
  doi =		{10.4230/LIPIcs.ICALP.2025.52},
  annote =	{Keywords: Property Testing, Relative Error}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.134
A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions

Authors: Penghui Yao and Mingnan Zhao

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Developing explicit pseudorandom generators (PRGs) for prominent categories of Boolean functions is a key focus in computational complexity theory. In this paper, we investigate the PRGs against the functions of degree-d polynomial threshold functions (PTFs) over Gaussian space. Our main result is an explicit construction of PRG with seed length poly(k, d, 1/ε)⋅log n that can fool any function of k degree-d PTFs with probability at least 1 - ε. More specifically, we show that the summation of L independent R-moment-matching Gaussian vectors ε-fools functions of k degree-d PTFs, where L = poly(k, d, 1/ε) and R = O(log kd/ε). The PRG is then obtained by applying an appropriate discretization to Gaussian vectors with bounded independence.
Cite as

Penghui Yao and Mingnan Zhao. A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 134:1-134:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yao_et_al:LIPIcs.ICALP.2025.134,
  author =	{Yao, Penghui and Zhao, Mingnan},
  title =	{{A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{134:1--134:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.134},
  URN =		{urn:nbn:de:0030-drops-235112},
  doi =		{10.4230/LIPIcs.ICALP.2025.134},
  annote =	{Keywords: Pseudorandom generators, polynomial threshold functions}
}
  • Refine by Type
  • 32 Document/PDF
  • 18 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 15 2025
  • 2 2024
  • 2 2022
  • 4 2021
  • Show More...

  • Refine by Author
  • 9 De, Anindya
  • 9 Servedio, Rocco A.
  • 5 Chen, Xi
  • 4 Nadimpalli, Shivam
  • 2 Hoza, William M.
  • Show More...

  • Refine by Series/Journal
  • 31 LIPIcs
  • 1 DARTS

  • Refine by Classification
  • 7 Theory of computation → Pseudorandomness and derandomization
  • 5 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 3 Mathematics of computing → Probabilistic inference problems
  • 2 Mathematics of computing
  • 2 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 4 pseudorandomness
  • 3 pseudorandom generators
  • 2 Property Testing
  • 2 Tolerant Property Testing
  • 2 algorithmic statistics
  • 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