- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates record-edit robustness under shared corruption budgets, addressing how to certify or manipulate report outcomes when audit logs contain both missing values (erasures ) and explicit mismatches (corruptions ).
Critical strengths
S1. Elegantly Formalized Theoretical Mechanics: The paper establishes a sound, mathematically rigorous framework for coupled corruption-edit dynamics. The Survivor-Aligned Normal Form is a genuinely neat theoretical insight that simplifies target search spaces, and the authors commendably prove its precise boundary conditions (Proposition 1) rather than ignoring edge cases.
S2. Sharp Parameterized Complexity Characterization: The paper offers a complete theoretical treatment of the problem's computational hardness, establishing a clear contrast with standard anchoring via a W[1]-hardness proof for explicit tables alongside a working FPT dynamic programming route over ordered binary decision branching programs.
Critical weaknesses
W1. Venue and Topic Fit. The paper's core contributions lie in formal logic, parameterized complexity, abductive explainability, and database causality. It contains no learning dynamics, representation learning, or neural architectures. Submitting this work to mainstream machine learning venues (such as ICLR, NeurIPS, or ICML) is a clear mismatch. The paper is vastly better aligned with formal methods, logic, and database theory venues—such as KR, CAV, SAT, PODS, ICDT.
W2. Restricted Real-World Applicability. Binary Feature Abstraction: Restricting the feature space strictly to binary vectors () limits direct deployment to real-world database records, financial transaction logs, and audit trails, which are inherently multi-valued, continuous, or relational.
W3. Fragile Unit-Cost Requirement (): The core theoretical engine depends entirely on erasing a field () costing the exact same unit budget as intentionally falsifying a value (). Proposition 1 explicitly proves that when , the survivor-aligned normal form breaks down. In real-world security and data auditing, erasing a record entry and actively forging a field value carry fundamentally different operational costs, adversary constraints, and detection risks.
W4. Empirically Weak Evaluation Lacking Scalability. In-Memory Baselines Outperform Symbolic Solvers: Experiments are restricted to tiny dimensions ( for SCMs, for DP programs). At these small scales, a naive in-memory Bitset search dramatically outperforms both General and Normal symbolic SAT solvers (e.g., at , Bitset finishes in 0.32s vs. Normal SAT's 1.02s and General SAT's 1.27s). The PySAT/Glucose3 solver setup introduces overhead that defeats the purpose of symbolic execution on the tested benchmarks.
W5. Missing Standard Optimization Baselines: The evaluation compares symbolic search against a brute-force Bitset search, but completely ignores standard formal verification and optimization baselines—such as MaxSAT, Integer Linear Programming (ILP/Gurobi), or SMT solvers (Z3, CVC5)—leaving the actual utility of the proposed DP/SAT implementation unverified at scale.
Questions for authors
Critical weaknesses W1--W5.
3 comments
Thank you for the detailed rebuttal and additional experiments. While the clarifications and new results are helpful, they do not fully address my main concerns.
First, the proposed model remains restrictive compared to real-world data auditing scenarios, particularly regarding data types and corruption costs. Second, although the additional experiments improve the evaluation, they still do not convincingly demonstrate scalability or clear practical advantages over simpler search methods and standard optimization baselines.
Overall, I appreciate the authors' efforts, but the rebuttal does not sufficiently change my assessment. I will maintain my original rating.
Thank you for considering the additional results and clarifying the remaining concerns. Appendix I.1 extends the setting to finite categorical fields and specifies admissible action costs; equal missing and mismatch charges within each field remain essential. The central contribution is the normal form’s preservation of minimum target-edit cost and protected-set blocking, together with the same-table complexity separation. The additional experiments examine the resulting protection decisions and computational costs, including cases where simpler methods are faster.
Response to Reviewer E5Qs
Thank you for the questions about learned models and optimization baselines.
W1. ... venue ... topic fit ...
Answer: Different inputs compatible with a damaged record can receive different predictions from a trained classifier. We added a Connect-4 experiment (Section 6.4, Table 5, p. 10) asking which squares protect a frozen classifier’s win/non-win report. We erased one square on each of 128 held-out boards. At filter budget one, 118 initially definite reports could reverse within two edits. Two protected squares could block reversal on 56 of those 118 boards. On 27 of the 56, all 861 pairs tied for delaying the first nonempty report change, yet only one to four pairs per board blocked reversal. On the other 29, every first-change optimum blocked it. Appendix I.2, Table 17, identifies the unique blocking pair on one board. A first-change tie can therefore conceal a consequential protection choice.
W2. ... Binary Feature Abstraction ...
Answer: Appendix I.1 extends Theorem 2 to arbitrary finite categorical fields with binary labels and equal missing and mismatch charges within each field. Fix a world surviving the final edit. Erasing a new write that disagrees with this survivor preserves its charge and never lowers any other world’s charge. When erasing an observed field costs at most rewriting it, costs are positive and additive over changed fields, and the replacement is admissible, this preserves the singleton target without increasing cost or introducing any new edited field. Both the minimum cost and protected-set blocking are preserved. The appendix also gives the unit-cost DP bound for a supplied complete ordered multiway program. In the Connect-4 experiment, an observed blank is a third square value, distinct from missing. Spambase uses threshold predicates on numerical features (Appendix I.3, Table 19). Raw continuous edits and edits subject to relational constraints need their own admissibility conditions.
W3. ... Fragile Unit-Cost Requirement ...
Answer: The auditor counts damaged fields. Its charge can vary by field, with missing and wrong values charged equally within a field. For the editor, Appendix I.1 allows erasing an observed value to cost less than rewriting it, provided the erasure is admissible, change costs are positive and additive, and unchanged fields cost zero. Proposition 1 shows why unequal within-field damage charges can break normalization. Operational detection risk is outside this model. We also ran an additional sensitivity experiment at all breakpoints of the auditor's missing charge λ, keeping mismatch and edit costs at one (Appendix I.5, Tables 21–22). The two protection objectives in Table 4 have disjoint optima throughout 0<λ≤1. At λ=1/2, protecting trial and restore blocks both reversal and empty support within two edits. At λ=1, every pair permits empty support after one edit. All 18 SCM queries retain their initial reports and target radii for 3/4<λ≤1. At λ=1/2, ten of the eighteen admit no nonempty change within budget.
W4. ... Scalability ... In-Memory Baselines ...
Answer: In the original SCM comparison, Bitset beat both symbolic methods on 16/18 queries. Both symbolic methods were faster on two 16-root layered queries, and Normal had no stable timing advantage over General (Table 2). The original DP study reached 512 fields on supplied programs of width five or seven. All three queries at that size had radius two and took 0.014–0.068 seconds for inference over roughly 1.18×10107 admissible strings (Appendix D). Section 6.3 adds two source-compilation experiments. All eight bounded P protocol configurations passed source checking. A shared check settled 32/64 queries, and DP was faster than enumeration on 12 of the 32 requiring search. Four of nine Spambase tree/order configurations passed source checking. Two hit the node cap and three timed out during proof checking. Enumeration was faster on all 32 completed comparisons requiring search (Appendix I.3, Tables 18–19).
W5. ... Standard Optimization Baselines ...
Answer: Section 6.2 adds a weighted partial MaxSAT baseline (RC2) on the original 18 SCM queries. We ran all four methods three times per query with the same external limits of 30 seconds per producer or checker stage, 512 MiB of memory and 32 MiB of output. A common checker rebuilt the labels, verified each witness and exhausted all lower-cost records. All 216 runs passed. Comparing per-query median worker times for preparation, solving and checking, MaxSAT was faster than General on 15/18 queries and Normal on 14/18. Bitset was faster than MaxSAT on all 18. With process startup included, MaxSAT beat Bitset on 5/18. Appendix I.4, Table 20, reports both measures and describes the encoding and proof costs.