Abstract. Given a graph [Formula: see text] and an integer [Formula: see text], let [Formula: see text] denote the minimum number of colors required to color the edges of [Formula: see text] such that, in each color class, the subgraph induced by the edges of that color has all nonzero degrees congruent to 1 modulo [Formula: see text]. In 1992, Pyber proved that [Formula: see text] for every graph [Formula: see text], and posed the question of whether [Formula: see text] can be bounded solely in terms of [Formula: see text] for every [Formula: see text]. This question was answered in 1997 by Scott, who showed that [Formula: see text], and further asked whether [Formula: see text]. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively proving that [Formula: see text], and conjectured that the multiplicative constant could be reduced to 1. A step towards this latter conjecture was made in 2024 by Nweit and Yang, who improved the bound to [Formula: see text]. In this paper, we further improve the multiplicative constant to 9. More specifically, we prove that there is a function [Formula: see text] for which [Formula: see text] if [Formula: see text] is odd, and [Formula: see text] if [Formula: see text] is even. In doing so, we prove that [Formula: see text] for every [Formula: see text]-degenerate graph [Formula: see text], which plays a central role in our proof.

Abstract We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $${\rm TC}^0$$ TC 0 -Frege. This extends the line of results of Krajííček and Pudlík( Information and Computation , 1998), Bonet, Pitassi, and Raz ( SIAM Journal on Computing , 2000),and Bonet, Domingo, Gavaldá, Maciel, and Pitassi ( Computational Complexity, 2004 ), who showed that ExtendedFrege, $${\rm TC}^0$$ TC 0 -Frege and $${\rm AC}^0$$ AC 0 -Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.

The complexity class CLS was introduced by Daskalakis and Papadimitriou (SODA 2010) to capture the computational complexity of important TFNP problems solvable by local search over continuous domains and, thus, lying in both PLS and PPAD. It was later shown that, e.g., the problem of computing fixed points guaranteed by Banach’s fixed point theorem is CLS-complete by Daskalakis et al. (STOC 2018). Recently, Fearnley et al. (J. ACM 2023) disproved the plausible conjecture of Daskalakis and Papadimitriou that CLS is a proper subclass of PLS∩PPAD by proving that CLS = PLS∩PPAD. To study the possibility of other collapses in TFNP, we connect classes formed as the intersection of existing subclasses of TFNP with the phenomenon of feasible disjunction in propositional proof complexity; where a proof system has the feasible disjunction property if, whenever a disjunction F ∨ G has a small proof, and F and G have no variables in common, then either F or G has a small proof. Based on some known and some new results about feasible disjunction, we separate the classes formed by intersecting the classical subclasses PLS, PPA, PPAD, PPADS, PPP and CLS. We also give the first examples of proof systems which have the feasible interpolation property, but not the feasible disjunction property.

Federated Learning (FL) has been recently proposed for distributed model training at the edge. The principle of this approach is to aggregate models learned over distributed clients to obtain a new more general "averaged" model. The resulting model is then redistributed to clients for further training. To date, the most popular federated learning algorithm uses coordinate-wise averaging of the model parameters for aggregation (FedAvg). In this paper, we carry out a general mathematical convergence analysis to evaluate aggregation strategies in a FL framework. From this, we derive novel aggregation algorithms which are able to modify their model architecture by differentiating client contributions according to the value of their losses. Moreover, we go beyond the assumptions introduced in theory, by evaluating the performance of these strategies and by comparing them with the one of FedAvg in classification tasks in both the IID and the non-IID framework.