Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SONGHUA HE:
All reports by Author Songhua He:

TR24-173 | 29th October 2024
Songhua He, Yuanzhi Li, Periklis Papakonstantinou, Xin Yang

Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL

This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL). ... more >>>


TR22-159 | 18th November 2022
Songhua He, Periklis Papakonstantinou

Deep Neural Networks: The Missing Complexity Parameter

Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>>




ISSN 1433-8092 | Imprint