More Like this

1. Fooling Polytopes

   https://doi.org/10.1145/3460532  

   O’Donnell, Ryan; Servedio, Rocco A.; Tan, Li-Yang (April 2022, Journal of the ACM)

   We give a pseudorandom generator that fools m -facet polytopes over {0, 1} n with seed length polylog( m ) · log n . The previous best seed length had superlinear dependence on m . 

   more » « less
2. Fooling polynomials using invariant theory

   https://doi.org/10.1109/FOCS54457.2022.00045  

   Derksen, Harm; Viola, Emanuele (October 2022, FOCS)
3. Fooling Network Interpretation in Image Classification

   Akshayvarun Subramanya, Vipin Pillai (January 2019, International Conference on Computer Vision (ICCV) 2019)

   Deep neural networks have been shown to be fooled rather easily using adversarial attack algorithms. Practical methods such as adversarial patches have been shown to be extremely effective in causing misclassification. However, these patches are highlighted using standard network interpretation algorithms, thus revealing the identity of the adversary. We show that it is possible to create adversarial patches which not only fool the prediction, but also change what we interpret regarding the cause of the prediction. Moreover, we introduce our attack as a controlled setting to measure the accuracy of interpretation algorithms. We show this using extensive experiments for Grad-CAM interpretation that transfers to occluding patch interpretation as well. We believe our algorithms can facilitate developing more robust network interpretation tools that truly explain the network’s underlying decision making process. 

   more » « less
4. Fooling Constant-Depth Threshold Circuits (Extended Abstract)

   https://doi.org/10.1109/FOCS52979.2021.00019  

   Hatami, Pooya; Hoza, William M.; Tal, Avishay; Tell, Roei (February 2022, Annual Symposium on Foundations of Computer Science)

   We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth d∈N and n1+δ wires, where δ=2−O(d) , using seed length O(n1−δ) and with error 2−nδ . This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds. Our second contribution is a PRG for De Morgan formulas of size s whose seed length is s1/3+o(1)⋅polylog(1/ϵ) for error ϵ . In particular, our PRG can fool formulas of sub-cubic size s=n3−Ω(1) with an exponentially small error ϵ=exp(−nΩ(1)) . This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currently-known lower bounds for this class. In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural “hybrid computational model” that combines several computational models. 

   more » « less
5. Fooling LiDAR Perception via Adversarial Trajectory Perturbation

   https://doi.org/10.1109/iccv48922.2021.00780  

   Li, Yiming; Wen, Congcong; Juefei-Xu, Felix; Feng, Chen (October 2021, 2021 IEEE/CVF International Conference on Computer Vision (ICCV))