- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper considers learning sparse parity functions of special block-wise structure (given by equation (3)). The results concern the complexity of learning of such functions by statistical queries. The paper is purely theoretical. Some of the results are formalized in Lean.
Critical strengths
The paper probably develops a coherent mathematical theory with some new results, but it is hard to assess and appreciate this theory for a human reader.
Critical weaknesses
Very poor exposition
The paper is extremely hard to read. It reads like written by AI and for AI. I'm not an expert in the narrow topic of the paper, but I'm familiar with some of the publications in the reference list, and they are by a large margin more readable.
The paper essentially assumes that the reader knows very well a very specialized line of previous research on hierarchical parity learning by statistical queries. The exposition is extremely dense and from the very beginning full of narrow terminology, which is never clarified ("parity characters", "rounds", "immediate interactions", "carrier", "unary witness", etc). Already the first equation (1) contains objects that are never formally defined in the main text. No broad context is explained. Motivation, state of the art, specific challenges to be addressed are very poorly explained. No heuristics, simple examples, practical experiments, graphical illustrations are provided. The contributions are stated in section 1.1 in an equally unclear form, with Theorem 1.1 being both informal and vague.
This lack of clarity cannot be justified. For example, the cited paper Cornacchia and Mossel (2023) is on the same topic of parity learning, but is perfectly readable even by non-experts, has a gentle, highly informative introduction, a clear contribution, helpful heuristics, examples and experiments.
I believe that the paper needs a major revision performed with a human reader in mind.
Questions for authors
N/A