Error correcting codes encode messages by codewords in such a way that even if some of the codeword is corrupted, the message can be decoded. Typical decoding algorithms for error correcting codes either use linear space or quadratic time. A natural question is whether codes can be decoded in near-linear time and sub-linear space simultaneously. A recent result by Cook and Moshkovitz gave efficient decoders that can uniquely decode Reed-Muller and other codes from a constant fraction (less than half) of corruption. In this work, we address the problem of list decoding in near-linear time and sub-linear space. In the list decoding setting, most of the codeword is corrupted, and one wants to output a short list of potential messages that contains the true message. For any constants γ, τ > 0, we give decoders for Reed-Muller codes that can decode from 1-γ fraction of corruptions in time n^{1+τ} and space n^{τ}. Our decoders work by extending the iterative correction technique of Cook and Moshkovitz. However, that technique, which gradually decreases the number of corruptions in the message, was tailored to the unique decoding setting. We first identify an intermediate problem, codewords list recovery, for which we can make iterative correction work. We then show how to reduce general list decoding to the codewords list recovery problem in efficient time and space. The reduction relies on local correction and testing. In the codewords list recovery problem, the input consists of n unordered lists containing exactly the symbols from L codewords, where a small fraction of the lists is corrupted. The goal is to find the L codewords. In addition, we prove that any linear code with time-space efficient encoding or decoding must be local, in the sense that the codewords satisfy a local linear constraint. This rules out codes like Reed-Solomon from having time-space efficient encoding or decoding.

We point out an error in the paper "Linear Time Encoding of LDPC Codes" (by Jin Lu and José M. F. Moura, IEEE Trans). The paper claims to present a linear time encoding algorithm for every LDPC code. We present a family of counterexamples, and point out where the analysis fails. The algorithm in the aforementioned paper fails to encode our counterexample, let alone in linear time.

Cooperative coevolutionary algorithms prove effective in solving tasks that can be easily decoupled into subproblems. When applied to problems with high coupling (where the fitness depends heavily on specific joint actions), evolution is often stifled by the credit assignment problem. This is due to each agent evolving their policy using a shared evaluation function that is sensitive to the "noise" of all other agents' actions. Using fitness critics alleviates this problem by approximating a local model of an agent's contribution and using that signal as a fitness function. However, fitness critics suffer when the quality of the local approximation degrades. In this work, we present Global Aligned Local Error (GALE), a loss function that generates better credit-assigning local evaluations that aim to maximize the alignment of the local and global evaluations. In a multiagent exploration domain, we show GALE's ability to learn better credit assignment, which leads to improved teaming behavior.

Co-evolutionary algorithms have successfully trained agent teams for tasks such as autonomous exploration or robot soccer. However generally, such approaches seek a single strong team, whereas many real-world applications require agents to effectively cooperate across multiple teams. To adapt to different teammates, agents need to learn more general teamwork skills rather than a single team-specific role. Previous work primarily frames this as a fitness-shaping problem, providing high-quality but expensive evaluation methods to isolate an agent's contribution. In this work, we introduce Learned Evaluations for Robust Teaming (LERT), an approach that provides a local evaluation that leverages state trajectories of agents to better quantify their impact across multiple teams. The key insight of this work is that agent state trajectories and previous experiences carry sufficient information to map agent abilities to team performance. As a result, LERT cooperatively co-evolves agents to work together across arbitrary teams. While only using local information and significantly fewer team evaluations, LERT performs as well as-if not better than-current methods.

Coevolutionary algorithms have effectively trained multiagent teams to collectively solve complex problems. However, in many real-world applications, changes to the environment or agent functionality require agents to function well with multiple different teams. In this paper, we provide a counterfactual-state-based shaped fitness evaluation that provides an agent-specific signal that promotes effective cooperation across a variety of teams. The key insight leading to this result is that the shaped fitnesses across multiple teams can be aggregated because those performances are independent of each other. As a result, this approach leads to a single signal that captures an agent's performance across multiple teams. We show that this method provides significant improvement over standard multiagent fitness-shaped methods in learning robust cooperative behavior.

We give two results on the size of AC0 circuits computing promise majority. ε-promise majority is majority promised that either at most an ε fraction of the input bits are 1 or at most ε are 0. - First, we show super-quadratic size lower bounds on both monotone and general depth-3 circuits for promise majority. - For any ε ∈ (0, 1/2), monotone depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε))/(ln(ε))}). - For any ε ∈ (0, 1/2), general depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε²))/(2ln(ε))}). These are the first quadratic size lower bounds for depth-3 ε-promise majority circuits for ε < 0.49. - Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority. - For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone non uniform AC0 circuits of depth-(2 + 2 k) computing ε-promise majority with size Õ(n^{1/(1 - 2^{-k})}). - For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone uniform AC0 circuit of depth-(2 + 2 k) computing ε-promise majority with size n^{1/(1 - (2/3) ^k) + o(1)}. These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai [Miklós Ajtai, 1983] and Viola [Emanuele Viola, 2009] combined with a divide and conquer strategy.