@proceedings {697637,
	title = {Limitations of the Impagliazzo{\textendash}Nisan{\textendash}Wigderson pseudorandom generator against permutation branching programs.},
	journal = {Proceedings of the 27th International Computing and Combinatorics Conference (COCOON {\textquoteright}21)},
	volume = {13025},
	year = {2021},
	pages = {3-12},
	publisher = {Lecture Notes in Computer Science (Springer)},
	abstract = {
	Version History:\&nbsp;Preliminary version posted as ECCC TR21-108. Invited to\&nbsp;Algorithmica\&nbsp;Special Issue on COCOON {\textquoteright}21.



	Abstract:\&nbsp;Forthcoming

},
	url = {https://link.springer.com/chapter/10.1007/978-3-030-89543-3_1},
	author = {Edward Pyne and Salil Vadhan}
}
@presentation {697629,
	title = {Analyzing the differentially private Theil-Sen estimator for simple linear regression},
	journal = {Poster at the 7th Workshop on the Theory and Practice of Differential Privacy (TPDP {\textquoteright}21) {\textendash} July 2021},
	year = {2021},
	url = {https://arxiv.org/abs/2207.13289},
	author = {Jayshree Sarathy and Salil Vadhan}
}
@proceedings {678053,
	title = {Concurrent composition of differential privacy},
	journal = {19th Theory of Cryptography Conference (TCC {\textquoteright}21) },
	volume = {13043},
	year = {2021},
	pages = {582-604},
	publisher = {Lecture Notes in Computer Science (Springer)},
	abstract = {
	Version History:\&nbsp;Also appeared as a poster in TPDP {\textquoteleft}21 and PPML {\textquoteleft}21.\&nbsp;Preliminary version posted as CoRR abs/2105.14427 and Cryptology ePrint Archive Report 2021/1196.



	Abstract:\&nbsp;We initiate a study of the composition properties of interactive differentially private mechanisms. An interactive differentially private mechanism is an algorithm that allows an analyst to adaptively ask queries about a sensitive dataset, with the property that an adversarial analyst{\textquoteright}s view of the interaction is approximately the same regardless of whether or not any individual{\textquoteright}s data is in the dataset. Previous studies of composition of differential privacy have focused on non-interactive algorithms, but interactive mechanisms are needed to capture many of the intended applications of differential privacy and a number of the important differentially private primitives.



	We focus on concurrent composition, where an adversary can arbitrarily interleave its queries to several differentially private mechanisms, which may be feasible when differentially private query systems are deployed in practice. We prove that when the interactive mechanisms being composed are pure differentially private, their concurrent composition achieves privacy parameters (with respect to pure or approximate differential privacy) that match the (optimal) composition theorem for noninteractive differential privacy. We also prove a composition theorem for interactive mechanisms that satisfy approximate differential privacy. That bound is weaker than even the basic (suboptimal) composition theorem for noninteractive differential privacy, and we leave closing the gap as a direction for future research, along with understanding concurrent composition for other variants of differential privacy.

},
	url = {https://link.springer.com/chapter/10.1007/978-3-030-90453-1_20},
	author = {Salil Vadhan and Tianhao Wang}
}
@proceedings {671766,
	title = {Pseudorandom generators for read-once monotone branching programs},
	journal = {APPROX/ RANDOM 2021},
	volume = {2021},
	number = {18},
	year = {2021},
	pages = {58:1-58:21},
	publisher = {Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl Leibniz-Zentrum f{\"u}r Informatik },
	edition = {207},
	abstract = {
	Version History: Originally published as "Monotone branching programs: pseudorandomness and circuit complexity".\&nbsp;



	Previously published as "Pseudorandom generators for read-once monotone branching programs",\&nbsp;Electronic Colloquium on Computational Complexity (ECCC) Vol. 2021, Issue 18. Linked here:\&nbsp;https://eccc.weizmann.ac.il/report/2021/018/



	Abstract:\&nbsp;Motivated by the derandomization of space-bounded computation, there has been a long line of work on constructing pseudorandom generators (PRGs) against various forms of read-once branching programs (ROBPs), with a goal of improving the \(O(\log^2n)\) seed length of Nisan{\textquoteright}s classic construction\&nbsp;to the optimal \(O(\log n)\).



	In this work, we construct an explicit PRG with seed length \(\tilde{O}(\log n)\) for constant-width ROBPs that are monotone, meaning that the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. This result is complementary to a line of work that gave PRGs with seed length \(O(\log n)\) for (ordered) permutation ROBPs of constant width, since the monotonicity constraint can be seen as the {\textquotedblleft}opposite{\textquotedblright} of the permutation constraint.



	Our PRG also works for monotone ROBPs that can read the input bits in any order, which are strictly more powerful than read-once \(\mathsf{AC^0}\). Our PRG achieves better parameters (in terms of the dependence on the depth of the circuit) than the best previous pseudorandom generator for read-once \(\mathsf{AC^0}\), due to Doron, Hatami, and Hoza.



	Our pseudorandom generator construction follows Ajtai and Wigderson{\textquoteright}s approach of iterated pseudorandom restrictions. We give a randomness-efficient width-reduction process which proves that the branching program simplifies to an \(O(\log n)\)-junta after only \(O(\log \log n)\) independent applications of the Forbes-Kelley pseudorandom restrictions.

},
	url = {https://drops.dagstuhl.de/opus/volltexte/2021/14751/},
	author = {Dean Doron and Raghu Meka and Omer Reingold and Avishay Tal and Salil Vadhan}
}
@proceedings {671765,
	title = {Pseudodistributions that beat all pseudorandom generators},
	journal = {36th Annual Computational Complexity Conference (CCC {\textquoteright}21) },
	volume = {200},
	year = {2021},
	pages = {33:1-33:15},
	publisher = {Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl Leibniz-Zentrum f{\"u}r Informatik },
	abstract = {
	Version History:\&nbsp;Full Version posted as ECC TR21-019. Invited to\&nbsp;Theory of Computing\&nbsp;Special Issue on CCC {\textquoteright}21.



	Abstract:



	A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ordered branching programs whose seed length has a better dependence on the error parameter\&nbsp;\&nbsp;than the classic PRG construction of Nisan (STOC 1990 and Combinatorica 1992).In this work, we give an explicit construction of PRPGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a PRPG for ordered permutation branching programs of unbounded width with a single accept state that has seed length\&nbsp;\(\tilde{O}(\log^{3/2}n)\)\&nbsp; for error parameter\&nbsp;\(\&nbsp;\epsilon = 1/ \mathrm{poly}(n)\), where\&nbsp;\(n\)\&nbsp;is the input length. In contrast, recent work of Hoza et al. (ITCS 2021) shows that any PRG for this model requires seed length\&nbsp;\(\&nbsp;\Omega(\log^2n)\)\&nbsp;to achieve error \(\&nbsp;\epsilon = 1/ \mathrm{poly}(n)\).As a corollary, we obtain explicit PRPGs with seed length\&nbsp;\(\tilde{O}(\log^{3/2}n)\)\&nbsp;\&nbsp;and error\&nbsp;\(\&nbsp;\epsilon = 1/ \mathrm{poly}(n)\)\&nbsp;for ordered permutation branching programs of width\&nbsp;\(w = \mathrm{poly}(n)\&nbsp;\)with an arbitrary number of accept states. Previously, seed length\&nbsp;\(o(\log^2n)\) was only known when both the width and the reciprocal of the error are subpolynomial, i.e.\&nbsp;\(w= n^{o(1)}\&nbsp;\)\&nbsp;and \(\epsilon = 1/n^{o(1)}\)(Braverman, Rao, Raz, Yehudayoff, FOCS 2010 and SICOMP 2014).The starting point for our results are the recent space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadenijad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving PRPGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (personal communication, January 2021).

},
	url = {https://drops.dagstuhl.de/opus/volltexte/2021/14307/pdf/LIPIcs-CCC-2021-33.pdf},
	author = {Edward Pyne and Salil Vadhan}
}
@proceedings {670581,
	title = {Pseudorandom generators for unbounded-width permutation branching programs},
	journal = {12th Innovations in Theoretical Computer Science (ITCS {\textquoteright}21) },
	volume = {185},
	number = {7},
	year = {2021},
	pages = {1-20},
	publisher = {Leibniz International Proceedings in Informatics (LIPIcs)},
	abstract = {
	Version History:\&nbsp;



	Preliminary version posted on\&nbsp;ECCC TR20-138\&nbsp;(PDF version attached as ECCC 2020).



	Talks:\&nbsp;The ITCS talk for this paper, presented by\&nbsp;Edward Pyne, is currently available on YouTube; click the embedded link to view.\&nbsp;



	We prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of \(\tilde{O} (\log d + \log n . \log(1/\epsilon))\), assuming the program has only one accepting vertex in the final layer. Here, \(n\) is the length of the program, \(d\) is the degree (equivalently, the alphabet size), and \(\epsilon\) is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length \(\Omega (n \log d)\) to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random."



	Except when the program{\textquoteright}s width \(w\) is very small, this is an improvement over prior work. For example, when \(w = \mathrm{poly} (n)\)\&nbsp;and \(d = 2\), the best prior PRG for permutation branching programs was simply Nisan{\textquoteright}s PRG [Nisan, 1992], which fools general ordered branching programs with seed length \(O (\log (wn/\epsilon) \log n)\). We prove a seed length lower bound of \(\tilde{\Omega} (\log d + \log n . \log(1/\epsilon)) \)for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when\( \epsilon <= 1/\log n\), our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020].

},
	url = {https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=13546},
	author = {William M. Hoza and Edward Pyne and Salil Vadhan}
}
@inbook {670580,
	title = {When simple hash functions suffice.},
	booktitle = {Beyond the Worst-Case Analysis of Algorithms (Tim Roughgarden, ed.)},
	year = {2021},
	publisher = {Cambridge University Press},
	organization = {Cambridge University Press},
	address = {Cambridge, UK},
	url = {https://doi.org/10.1017/9781108637435.033},
	author = {Kai-Min Chung and Michael Mitzenmacher and Salil Vadhan}
}
@article {633639,
	title = {Deterministic approximation of random walks in small space},
	journal = {Theory of Computing Special Issue on APPROX-RANDOM {\textquoteright}19},
	volume = {17(4)},
	year = {2021},
	pages = {1-35},
	publisher = {Leibniz International Proceedings in Informatics (LIPIcs)},
	address = {Cambridge, Massachusetts (MIT) },
	abstract = {
	Version History: v1, 15 Mar.\&nbsp;2019:\&nbsp;https://arxiv.org/abs/1903.06361v1



	v2 in ArXiv, 25 Nov. 2019:\&nbsp;https://arxiv.org/abs/1903.06361v2



	\&nbsp;



	Prior Published Version\&nbsp;(APPROX-RANDOM 2019), 20 Sep 2019:\&nbsp;



	In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh (Eds.). Vol. 145. Cambridge, Massachusetts (MIT): Leibniz International Proceedings in Informatics (LIPIcs), 2019.



	http://drops.dagstuhl.de/opus/volltexte/2019/11257/



	\&nbsp;



	We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph\&nbsp;\(G\), a positive integer\&nbsp;\(r\), and a set\&nbsp;\(S\)\&nbsp;of vertices, approximates the conductance of\&nbsp;\(S\)\&nbsp;in the\&nbsp;\(r\)-step random walk on\&nbsp;\(G\)\&nbsp;to within a factor of\&nbsp;\(1+ϵ\), where\&nbsp;\(ϵ \&gt; 0\)\&nbsp;is an arbitrarily small constant. More generally, our algorithm computes an\&nbsp;\(ϵ\)-spectral approximation to the normalized Laplacian of the\&nbsp;\(r\)-step walk.\&nbsp;Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, 2005), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas from (Cheng, Cheng, Liu, Peng, and Teng, 2015), which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even\&nbsp;\(r\)\&nbsp;(while ours works for all\&nbsp;\(r\)). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd\&nbsp;\(r\). Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.

},
	url = {http://theoryofcomputing.org/articles/v017a004/},
	author = {Jack Murtagh and Omer Reingold and Aaron Sidford and Salil Vadhan}
}
