More Like this

1. Monotone-Policy BARGs and More from BARGs and Quadratic Residuosity

   Nassar, Shafik; Waters, Brent; Wu, David J (May 2025, Springer)

   We say a tuple of NP statements satisfies a monotone policy if , where if and only if is in the NP language. A monotone-policy batch argument (monotone-policy BARG) for NP is a natural extension of regular batch arguments (BARGs) that allows a prover to prove that satisfy a monotone policy P with a proof of size , where is the size of the Boolean circuit computing the NP relation . Previously, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) and Nassar, Waters, and Wu (TCC 2024) showed how to construct monotone-policy BARGs from (somewhere-extractable) BARGs for NP together with a leveled homomorphic encryption scheme (Brakerski et al.) or an additively homomorphic encryption scheme over a sufficiently-large group (Nassar et al.). In this work, we improve upon both works by showing that BARGs together with additively homomorphic encryption over any group suffices (e.g., over). For instance, we can instantiate the additively homomorphic encryption with the classic Goldwasser-Micali encryption scheme based on the quadratic residuosity (QR) assumption. Then, by appealing to existing compilers, we also obtain a monotone-policy aggregate signature scheme from any BARG and the QR assumption. 

   more » « less
2. Certification with an NP oracle

   Guy Blanc; Caleb Koch; Lange, Jane; Strassle, Carmen Tan (January 2023, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023))

   In the certification problem, the algorithm is given a function f with certificate complexity k and an input x^⋆, and the goal is to find a certificate of size ≤ poly(k) for f’s value at x^⋆. This problem is in NP^NP, and assuming 𝖯 ≠ NP, is not in 𝖯. Prior works, dating back to Valiant in 1984, have therefore sought to design efficient algorithms by imposing assumptions on f such as monotonicity. Our first result is a BPP^NP algorithm for the general problem. The key ingredient is a new notion of the balanced influence of variables, a natural variant of influence that corrects for the bias of the function. Balanced influences can be accurately estimated via uniform generation, and classic BPP^NP algorithms are known for the latter task. We then consider certification with stricter instance-wise guarantees: for each x^⋆, find a certificate whose size scales with that of the smallest certificate for x^⋆. In sharp contrast with our first result, we show that this problem is NP^NP-hard even to approximate. We obtain an optimal inapproximability ratio, adding to a small handful of problems in the higher levels of the polynomial hierarchy for which optimal inapproximability is known. Our proof involves the novel use of bit-fixing dispersers for gap amplification. 

   more » « less
3. Automating algebraic proof systems is NP-Hard

   Göös, M; Nordström, J; Pitassi, T; Robere, R; de Rezende, Susanna F; Sokolov, D. (May 2020, Electronic colloquium on computational complexity)

   We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Muller (FOCS 2019) that established an analogous result for Resolution. 

   more » « less
4. Regularization of Low Error PCPs and an Application to MCSP

   https://doi.org/10.4230/LIPIcs.ISAAC.2023.39  

   Hirahara, Shuichi; Moshkovitz, Dana (November 2023, 34th International Symposium on Algorithms and Computation (ISAAC 2023))

   Iwata, Satoru; Kakimura, Naonori (Ed.)

   In a regular PCP the verifier queries each proof symbol in the same number of tests. This number is called the degree of the proof, and it is at least 1/(sq) where s is the soundness error and q is the number of queries. It is incredibly useful to have regularity and reduced degree in PCP. There is an expander-based transformation by Papadimitriou and Yannakakis that transforms any PCP with a constant number of queries and constant soundness error to a regular PCP with constant degree. There are also transformations for low error projection and unique PCPs. Other PCPs are constructed especially to be regular. In this work we show how to regularize and reduce degree of PCPs with a possibly large number of queries and low soundness error. As an application, we prove NP-hardness of an unweighted variant of the collective minimum monotone satisfying assignment problem, which was introduced by Hirahara (FOCS'22) to prove NP-hardness of MCSP^* (the partial function variant of the Minimum Circuit Size Problem) under randomized reductions. We present a simplified proof and sufficient conditions under which MCSP^* is NP-hard under the standard notion of reduction: MCSP^* is NP-hard under deterministic polynomial-time many-one reductions if there exists a function in E that satisfies certain direct sum properties. 

   more » « less
5. Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees

   https://doi.org/10.1137/1.9781611978322.33  

   Gupta, Swati; Moondra, Jai; Singh, Mohit (January 2025, Society for Industrial and Applied Mathematics)

   Motivated by fairness concerns, we study existence and computation of portfolios, defined as: given anoptimization problem with feasible solutions D, a class C of fairness objective functions, a set X of feasible solutions is an α-approximate portfolio if for each objective f in C, there is an α-approximation for f in X. We study the trade-off between the size |X| of the portfolio and its approximation factor αfor various combinatorial problems, such as scheduling, covering, and facility location, and choices of C as top-k, ordered and symmetric monotonic norms. Our results include: (i) an α-approximate portfolio of size O(log d*log(α/4))for ordered norms and lower bounds of size \Omega( log dlog α+log log d)for the problem of scheduling identical jobs on d unidentical machines, (ii) O(log n)-approximate O(log n)-sized portfolios for facility location on n points for symmetric monotonic norms, and (iii) logO(d)^(r^2)-size O(1)-approximate portfolios for ordered norms and O(log d)-approximate for symmetric monotonic norms for covering polyhedra with a constant rnumber of constraints. The latter result uses our novel OrderAndCount framework that obtains an exponentialimprovement in portfolio sizes compared to current state-of-the-art, which may be of independent interest. 

   more » « less