Grotle

Review of "Excluding paths and bicliques"

## Summary
This paper presents significant improvements on bounds for path number and treedepth in graphs that exclude a path and a biclique as induced subgraphs. The authors improve the best known bound on the path number to a singly exponential function of the clique number, which they show is optimal up to constant factors. They also demonstrate that treedepth is polynomially bounded by the clique number for such graphs, leading to a treedepth analogue of a recent result on pathwidth.

## Mathematical/empirical assessment
The paper provides rigorous proofs for its main results, including improved bounds on path number and treedepth. The authors leverage known results about pathwidth and use a combination of structural graph theory and combinatorial arguments to establish their claims. The exponential bound on path number is shown to be tight through explicit constructions, and the polynomial bound on treedepth is derived using a linear relationship between treedepth and pathwidth for P_s-free graphs.

## Strengths
- The paper makes substantial progress on a well-studied problem in structural graph theory.
- The results are both theoretically significant and have implications for algorithmic properties of graph classes.
- The proofs are clear and well-structured, with careful attention to technical details.
- The paper connects its results to broader concepts like clique-polynomiality and highlights the importance of excluding certain subgraphs.

## Concerns
- While the paper is technically sound, some of the more complex arguments could benefit from additional intuition or examples to aid understanding.
- The paper assumes familiarity with advanced concepts in graph theory, which may limit accessibility for some readers.

## Final decision
Strong accept

Summary
The paper introduces HarmQ, a quantum-native backdoor attack method targeting Quantum Neural Networks (QNNs). It addresses the challenges of classical backdoor attacks failing in quantum systems due to downsampling and spectral learning bias of parameterized quantum circuits (PQCs). HarmQ uses sinusoidal perturbations on coarse grids with block-uniform structure, ensuring survival through downsampling while aligning with PQCs' preference for low-frequency components. The method achieves high attack success rates (over 99%) while maintaining clean accuracy (over 90%) on MNIST and Fashion-MNIST datasets.

Mathematical/empirical assessment
The paper provides a detailed analysis of why classical triggers fail in QNNs, particularly due to downsampling and the spectral learning bias of PQCs. It introduces a mathematical formulation for the sinusoidal trigger pattern and demonstrates its effectiveness through experiments. The results show that HarmQ outperforms existing methods like BadNets, Watermark, Q-FGSM, and QUAP in terms of attack success rate (ASR) while maintaining high clean accuracy. Parametric t-SNE visualizations confirm that harmonic triggers create distinct clusters in quantum state representations.

Strengths
- The paper presents a novel and effective approach to backdoor attacks in QNNs, addressing key challenges specific to quantum systems.
- The method is robust across different QNN architectures and downsampling techniques.
- Empirical results demonstrate high ASR and clean accuracy, validating the effectiveness of the proposed approach.

Concerns
- The paper does not provide detailed information about the implementation of the quantum circuit simulations or the specific hyperparameters used in the experiments.
- The theoretical analysis of the Fourier decomposition bias of PQCs is somewhat brief and could be expanded for clarity.

Final decision
Strong accept