Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles".
Jane: Here's the gist of the paper. For a matrix over a field of characteristic two, let Φ(A) be the sum of its permutation monomials indexed by odd permutations; this parity sub-sum retains information that neither gives separately The result includes singular matrices and the binary field Applied to Φ(I + zW) for a randomly weighted adjacency matrix W, the evaluator computes the shortest even directed-cycle length in Oe(nτ+1) bit operations, improving the Oe(nτ+3) bound of Björklund, Husfeldt, and Kaski with the same multiplication exponent Fast Evaluation and Differentiation The authors show that Φ(A) and all its first partial derivatives can be computed deterministically in O(nτ) field operations for every n × n matrix, where 2 < τ ≤ 3 is any fixed admissible matrix multiplication exponent This result includes singular matrices and the binary field.
Tom: An inversion-count identity expresses Φ through complementary minors <ref:2609.12021#pg5> For invertible matrices, a decomposition along two binary interval trees aggregates these minors by matrix multiplication; a Boolean border of constant size handles the remaining ranks <ref:2609.12021#pg6> Graph Algorithm Efficiency The combinatorial application is the shortest even directed-cycle problem <ref:2609.12021#pg3>, and Theorem 1.2 states that for a simple directed graph on n vertices, a randomized algorithm computes the shortest even-cycle length and the union of the arc sets of all shortest even cycles in Oe(nτ+1) bit operations <ref:2609.12021#pg7> Theorem 1.3 provides an actual shortest cycle with worst-case running time Oe(n4) that outputs a shortest even directed cycle with probability 1 − O(n − 3) whenever one exists <ref:2609.12021#pg8> Algebraic Mechanism and Bounds The algebraic mechanism involves the inversion count of a permutation being its oddness indicator <ref:2609.12021#pg4>, and expanding this count gives a sum of products of two entries and a complementary determinant <ref:2609.12021#pg5> The evaluation of these traces with the smaller output dimension and summing over all scales costs O(nτ) <ref:2609.12021#pg12> Proposition 4.2 states that the value Φ(A) of any n × n matrix over any characteristic-two field can be computed deterministically in O(nτ) field operations <ref:2609.12021#pg3> Witness Extraction Techniques The paper presents three methods for extracting a shortest even cycle, including exact maintenance which provides a general fourth-degree bound and the stronger parameter bounds in Appendix A <ref:2609.12021#pg2> Method A.1 involves querying whether a subgraph contains an l-cycle using Lemma 7.1 to find an arc set of size l <ref:2609.12021#pg4> Method A.2 involves vertex deletion rounds, and Proposition A.3 provides a combined parameter bound for returning a shortest even cycle with probability 1 − O(n − 3) <ref:2609.12021#pg5> The algorithm can use O(n 3) field elements; quadratic space is separately available for Proposition A.3 <ref:2609.12021#pg5> Relation to Earlier Work The paper notes that the parity cycle-cover polynomial and its relation to the permanent and determinant originate in the framework of Vazirani and Yannakakis
VY89: <ref:2609.12021#pg9> The authors use this proportional-row expansion and do not claim it as a new combinatorial device <ref:2609.12021#pg10> The result is a uniform matrix multiplication bound over every characteristic-two field, including all singular inputs <ref:2609.12021#pg2> All fast bounds include the rank, inverse, interpolation, and polynomial arithmetic costs <ref:2609.12021#pg5> The scalar and gradient algorithms can use quadratic workspace; direct truncated-series extraction can require cubic workspace <ref:2609.12021#pg3> The paper's organization is structured with Section 2 giving notation and algebraic tools <ref:2609.12021#pg2> Sections 3–5 prove Theorem 1.1 <ref:2609.12021#pg3>, Section 6 proves the graph length, support, and uniqueness results <ref:2609.12021#pg2>, Section 7 gives the general witness algorithm, and Appendix A proves the parameter bounds <ref:2609.12021#pg3> The references listed include
BH74: James R.
Jane: Bunch and John E.
Tom: Hopcroft <ref:2609.12021#pg5>
BHK24: Andreas Björklund, Thore Husfeldt, and Petteri Kaski <ref:2609.12021#pg5>
BHL17: Andreas Björklund, Thore Husfeldt, and Isak Lyckberg <ref:2609.12021#pg5>
BKK14: Andreas Björklund, Petteri Kaski, and Łukasz Kowalik <ref:2609.12021#pg5>
BKR09: Mark Braverman, Raghav Kulkarni, and Sambuddha Roy <ref:2609.12021#pg5>
BS83: Walter Baur and Volker Strassen <ref:2609.12021#pg5>
CK91: David G.
Title and authors: Tom: So we're looking at this paper today. It's called "Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles." And it tackles two things: how to calculate a specific sum of permutations, and finding the shortest even directed cycle in a graph.
Jane: That sounds pretty technical right away, Tom. Can you tell us what that sum actually is? What's the big deal with calculating only the odd permutations when you have a matrix over a field of characteristic two?
Tom: Well, page one explains that this sum, which they call Phi of A, is something that even if you have a determinant or a permanent, it doesn't give you all the information. It keeps track of some other stuff about the matrix structure.
Lu: It seems like they’re focusing on this parity sub-sum because it retains information that neither the determinant nor the permanent gives separately > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
Meng: So, what's the main result they are showing for calculating Phi of A? Is it fast?
Tom: Yes, the big point is that they show you can compute Phi of A and all its first partial derivatives deterministically in O of n tau field operations. And this works for every n by n matrix over a field where two less than tau less than or equal to three, which is any fixed admissible matrix multiplication exponent > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1,is any fixed admissible matrix multiplication exponent>
Jane: O of n tau sounds efficient, but what does that actually mean for someone who just wants to know if their matrix calculation will take a long time?
Tom: It means it's fast. And here’s something important: this result includes singular matrices and even works over the binary field > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1,result includes singular matrices and>
Lu: That's significant because most fast algorithms assume the matrix is invertible, but they handle singular matrices too > Page one <ref:2609.12021#pg2> <ref:2609.12021#pg1>
Meng: Okay, that’s good for theory. But what about the graph part? The paper mentions finding the shortest even directed cycle. Is that where they actually use this calculation?
Tom: Exactly. The combinatorial application of this is figuring out the shortest even directed cycle problem > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1,the shortest even directed cycle>
Jane: So, if you take a randomly weighted adjacency matrix and apply this method, what does it tell you about finding that shortest even cycle length? Is it faster than what we already have?
Tom: They state they compute the shortest even directed cycle length in O of n tau plus one bit operations. And they say this improves upon the O of n tau plus three bound that Björklund, Husfeldt, and Kaski had before > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
Lu: That's a definite improvement in the complexity for that specific graph problem. It shows they’ve managed to squeeze out some efficiency there > Page two <ref:2609.12021#pg2> <ref:2609.12021#pg1>
Title and authors: Meng: O of n tau plus one is better than O of n tau plus three, but what's the practical impact on a large graph? Is it fast enough for real traffic?
Tom: Well, the point is that this improvement in the bit operations exponent means they can do this for weighted adjacency matrices with high probability > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
Jane: That’s good. But what about those exact shortest cycles they can find? Does this method give us a real cycle, or just a probability of finding one?
Tom: Theorem one point three says they have an actual shortest cycle with worst case running time of O of n to the fourth. And it outputs a shortest even directed cycle with probability one minus O of n minus three whenever one exists > Page one <ref:2609.12021#pg8> <ref:2609.12021#pg1>
Lu: So, there’s a tradeoff between getting a guaranteed result and getting something fast, which is typical in these kinds of problems > Page two <ref:2609.12021#pg2> <ref:2609.12021#pg1>
Meng: O of n to the fourth sounds slow for production systems. What are those exact running times we should be worried about when deploying this?
Tom: The paper also gives a method for extracting a shortest even cycle, Method A point one, which involves querying whether a subgraph contains an l cycle using Lemma seven point one to find an arc set of size l > Page two <ref:2609.12021#pg4> <ref:2609.12021#pg1>
Jane: So there are different ways to approach finding these cycles. Are we talking about something that’s guaranteed to work quickly, or is it more of a sampling process?
Tom: It’s a mix. Method A point two involves vertex deletion rounds, and proposition A point three gives you a combined parameter bound for returning a shortest even cycle with probability one minus O of n minus three > Page two <ref:2609.12021#pg5> <ref:2609.12021#pg1>
Lu: That probabilistic approach is interesting because it’s more feasible than the worst-case runtime, but we have to keep that failure probability in mind > Page two <ref:2609.12021#pg5> <ref:2609.12021#pg1>
Meng: If we're talking about deployment, what are the memory and field element costs for running these extraction methods? Can we actually fit this on hardware?
Tom: The algorithm can use O of n to the third field elements, but proposition A point three gives you a combined parameter bound that is quadratic space separately available > Page two <ref:2609.12021#pg5> <ref:2609.12021#pg1>
Jane: Quadratic space sounds manageable compared to cubic space. That's a relief for deployment considerations. So, what’s the underlying math driving this cycle finding? Where does it connect back to the initial sum of permutations?
Tom: The mechanism involves using the inversion count of a permutation as an indicator of its oddness > Page four <ref:2609.12021#pg4>
Lu: And expanding that count gives you a sum of products involving two entries and a complementary determinant > Page five <ref:2609.12021#pg5>
Meng: That sounds like heavy algebra. How does this algebraic expansion translate into the actual graph structure we’re looking for?
Title and authors: Tom: The evaluation of these traces with the smaller output dimension and summing over all scales costs O of n tau field operations > Page twelve <ref:2609.12021#pg12>
Jane: So, it seems the core idea is to use this algebraic mechanism to separate a static result from the dynamic operations needed to isolate a graph witness. Can you explain that separation more simply?
Tom: The paper says the complementary minor identity shows that Phi vanishes at corank at least three > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Lu: So, it means if something is singular in a specific way, we can handle those remaining singular ranks with at most four invertible bordered matrices, even over F two > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Meng: Four bordered evaluations sounds like a fixed small cost. That’s what I need to hear for scaling up the computation > Page two <ref:2609.12021#pg5> <ref:2609.12021#pg1>
Tom: Yes, that separation is key. The proportional-row identity then gives you an explicit full gradient formula > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Jane: So, that means we can move from the abstract algebraic result to something more concrete when we need to find a cycle > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Tom: Exactly. And the relation to earlier work shows this is building on ideas from Vazirani and Yannakakis VY89, but they aren't claiming it’s a new combinatorial device > Page ten <ref:2609.12021#pg10>
Lu: It seems like they’re using existing tools in a clever way, just applying them to this specific context of characteristic two fields > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Meng: What about the overall cost? If we combine the fast evaluation of Phi and the cycle finding, what's the total runtime we should be budgeting for a real application?
Tom: The overall result is that all fast bounds include costs for rank, inverse, interpolation, and polynomial arithmetic > Page five <ref:2609.12021#pg5>
Jane: That’s a lot of things included in that speed. So to wrap up this discussion on "Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles," what's the main message we should take away?
Tom: The main message is that you can compute these complex parity sums and find shortest even cycles with good complexity, even for singular matrices, using O of n tau field operations > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
Lu: It confirms that this algebraic machinery works deterministically and efficiently across various matrix types in characteristic two fields > Page three <ref:2609.12021#pg3> <ref:2609.12021#pg1>
Meng: For deployment purposes, the improvement in the cycle finding bound from O of n tau plus three to O of n tau plus one is important for our real-time needs > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
Jane: It’s a solid paper because it gives us deterministic speed for something that was previously harder to handle, and it shows how to connect abstract algebraic properties directly to concrete graph problems.
Tom: Exactly. We’ve got the fast tools now for handling these specific matrix operations and cycle detection > Page one <ref:2609.12021#pg1> <ref:2609.12021#pg1>
The paper's summary: Tom: So, we've been looking at how they can calculate this specific sum of permutations in characteristic two fields, and now we need to talk about what that actually means for finding cycles in a graph > Page one <ref:2609.12021#pg1>
Jane: Right, so the main thing is that they found a way to compute this parity sub-sum, Phi of A, and all its first partial derivatives deterministically. And they manage this even when the matrix is singular or we're working over the binary field > Page one <ref:2609.12021#pg1>
Lu: What's really interesting here is how they connect this algebraic sum to the shortest even directed cycle problem in graphs. They use an inversion count of a permutation as an indicator of its oddness > Page four <ref:2609.12021#pg4>
Meng: So, what does that mean for the graph itself? Does it give us a faster way to find the shortest even cycle than we already have?
Tom: Yes, they claim that this method computes the shortest even directed cycle length in O of n tau plus one bit operations. That's an improvement over a previous bound of O of n tau plus three > Page one <ref:2609.12021#pg1>
Jane: That improvement, from plus three to just plus one, is significant for real-time analysis when you're dealing with weighted adjacency matrices > Page two <ref:2609.12021#pg2>
Lu: It also gives us a way to get an actual shortest cycle. They have a method that finds it with a worst case running time of O of n to the fourth, and they say it works with high probability whenever one exists > Page one <ref:2609.12021#pg8>
Meng: O of n to the fourth is still pretty slow for production systems, but they also present some witness extraction techniques. They have methods that can give you an exact shortest cycle in O of n to the fourth time > Page two <ref:2609.12021#pg5>
Tom: That's one thing, but there are other ways to get a result. There's a method involving querying whether a subgraph has an l cycle using some lemma, which lets you find an arc set of size l > Page two <ref:2609.12021#pg4>
Jane: So, it sounds like they give us three distinct approaches to finding these shortest even cycles. One is the fast bit operation bound, another is the exact time bound for a general graph, and a third is this querying method > Page two <ref:2609.12021#pg5>
Lu: The underlying mechanism involves an inversion count of a permutation expanding into sums of products and complementary determinants > Page five <ref:2609.12021#pg5>
Meng: That's heavy algebra. How does that actually translate to finding the cycle structure? What's the practical cost when we try to run this on a large graph with many vertices?
Tom: The evaluation of these traces, summing over all scales, costs O of n tau field operations > Page twelve <ref:2609.12021#pg12>
Jane: So they are showing us that even though the math is complex, if you can evaluate these traces efficiently using that O of n tau cost, you get a good result for the graph problem > Page three <ref:2609.12021#pg3>
Lu: And there's this concept where they show that Phi vanishes at corank at least three. That means they can handle the remaining singular ranks with just a few more bordered matrices > Page three <ref:2609.12021#pg3>
Meng: Four bordered evaluations sounds like a fixed small cost, which is good for scaling up the computation > Page two <ref:2609.12021#pg5>
Tom: Exactly. And it's worth remembering that this whole framework builds on earlier work from Vazirani and Yannakakis, but they aren't claiming to be entirely new in that sense > Page ten <ref:2609.12021#pg10>
Jane: So, the big picture here is deterministic speed for complex matrix sums and a faster way to tackle a classic graph problem with weighted matrices > Page three <ref:2609.12021#pg3>
The paper's improvements: Tom: So, we've seen how they calculate that parity sum in O of n tau field operations, and now we're talking about what they suggest improving in this work > Page one <ref:2609.12021#pg1>
Jane: Right, so beyond just the speed of calculation, the authors suggest three different methods for finding those shortest even cycles > Page two <ref:2609.12021#pg5>
Lu: The first improvement is related to exact maintenance. They show you can get an actual shortest cycle with high probability in O of n to the fourth time for general graphs > Page two <ref:2609.12021#pg4>
Meng: O of n to the fourth is still not great for what we need in production, but they also have this method where you query whether a subgraph has an l cycle using some lemma > Page two <ref:2609.12021#pg4>
Tom: That querying method gives you an arc set of size l, and it's part of Method A point one > Page two <ref:2609.12021#pg4>
Jane: And then there's the vertex deletion rounds in Method A point two, which leads to this combined parameter bound for returning a shortest even cycle with high probability > Page two <ref:2609.12021#pg5>
Lu: That bound is what they call proposition A point three, and it's a better guarantee than just the exact time we saw earlier > Page two <ref:2609.12021#pg5>
Meng: So if I'm deploying this, the probabilistic approach seems more realistic than that worst-case running time for a general graph > Page two <ref:2609.12021#pg5>
Tom: That’s what they are pushing—moving from guaranteed worst-case performance to high probability results with better bounds > Page one <ref:2609.12021#pg1>
Jane: It sounds like they are trying to balance the need for a fast result with the need to actually find a correct cycle structure > Page two <ref:2609.12021#pg2>
Lu: The authors also mention that they can use quadratic space for proposition A point three, which is pretty helpful when you're talking about memory costs > Page two <ref:2609.12021#pg5>
Meng: Quadratic space is better than cubic space, which is what I was worried about when we thought about the extraction methods > Page two <ref:2609.12021#pg5>
Tom: Exactly. And they noted that this whole structure builds on earlier work, but they aren't claiming a brand new combinatorial device in that sense > Page ten <ref:2609.12021#pg10>
Jane: So, it’s not just a new idea from scratch, it’s clever application of existing algebraic tools to get better performance on this specific type of matrix problem > Page three <ref:2609.12021#pg3>
Lu: It shows how you can use the structure of the parity sub-sum to isolate the information needed for graph algorithms > Page five <ref:2609.12021#pg5>
Meng: I'm interested in knowing what happens if we try to apply this to a different kind of matrix, say one that isn't over a field of characteristic two > Page one <ref:2609.12021#pg1>
Tom: That’s the next step, I guess. We have the proof for characteristic two, but generalizing that is always going to be tricky > Page three <ref:2609.12021#pg3>
Conclusion: Tom: So, to wrap things up, this paper on "Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles" shows we can compute those complex parity sums deterministically in O of n tau field operations > Page one <ref:2609.12021#pg1>
Jane: And they provide a better way to find shortest even cycles than what was previously known, specifically improving the bound from O of n tau plus three to just O of n tau plus one bit operations > Page one <ref:2609.12021#pg1>
Lu: The authors are showing that this algebraic machinery works across every characteristic two field, including singular inputs, which is a solid piece of work > Page two <ref:2609.12021#pg2>
Meng: I still have my concerns about the practical costs for running these extraction methods on large graphs, but the quadratic space bound on proposition A point three is something to keep in mind > Page two <ref:2609.12021#pg5>
Lalam: I'm confident that their results are solid. The connection they made between the inversion count and the graph structure is very direct > Page five <ref:2609.12021#pg5>
Tom: It really does provide a concrete mechanism for moving from abstract algebraic properties to finding a graph witness, which is exactly what we needed > Page three <ref:2609.12021#pg3>
Jane: This work means we have better tools for analyzing weighted adjacency matrices in characteristic two fields, which is important for things like certain types of coding theory or cryptography > Page one <ref:2609.12021#pg1>
Lu: It opens the door to exploring how these techniques might be generalized to other algebraic structures, which is definitely a future direction > Page three <ref:2609.12021#pg3>
Meng: If we can get those extraction methods running on real traffic with that O of n tau plus one complexity, then it could actually be useful in real-time detection systems > Page two <ref:2609.12021#pg5>
Tom: Exactly. So the main thing is deterministic speed for these kinds of operations, and that's what this paper delivers > Page one <ref:2609.12021#pg1>
Jane: It’s a lot of math packed into one paper, but they really nail the connection between the sum and the cycle problem > Page three <ref:2609.12021#pg3>
Hanqing Li
Peking University
cs.DS
Submitted: 2026-09-10
Updated: 2026-11-08
Comments: 24 pages, no figures
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 100/100
The gist: For a matrix over a field of characteristic two, let Φ(A) be the sum of its permutation monomials indexed by odd permutations…
Key concepts
- $\Phi(A)$
- This is a specific sum calculated from a matrix A over a field of characteristic two. It involves summing up terms corresponding only to permutations that have an odd number of swaps (odd permutations). This quantity retains important information about the matrix structure.
- $O(n\tau)$ Field Operations
- This describes the computational complexity for evaluating $\Phi(A)$ and its derivatives. The complexity is linear in $n$ multiplied by a fixed matrix multiplication exponent $\tau$. This means the evaluation is very fast, even for large matrices, and works deterministically over any field of characteristic two.
- Shortest Even Directed Cycle
- This is a graph problem asking for the length of the shortest cycle in a directed graph where every edge traversal must result in an even number of steps. The paper provides efficient randomized and deterministic methods to find this cycle length, which is vital for analyzing network structures.
- Inversion Count Identity
- This identity expresses $\Phi(A)$ using complementary minors. For invertible matrices, it allows the calculation to be broken down into matrix multiplications involving binary interval trees and Boolean borders, providing an algebraic path to the fast evaluation.
Terminology
Summary
For a matrix over a field of characteristic two, let Φ(A) be the sum of its permutation monomials indexed by odd permutations; this parity sub-sum retains information that neither gives separately The result includes singular matrices and the binary field Applied to Φ(I + zW) for a randomly weighted adjacency matrix W, the evaluator computes the shortest even directed-cycle length in Oe(nτ+1) bit operations, improving the Oe(nτ+3) bound of Björklund, Husfeldt, and Kaski with the same multiplication exponent
Fast Evaluation and Differentiation
The authors show that Φ(A) and all its first partial derivatives can be computed deterministically in O(nτ) field operations for every n × n matrix, where 2 < τ ≤ 3 is any fixed admissible matrix multiplication exponent This result includes singular matrices and the binary field. An inversion-count identity expresses Φ through complementary minors <ref:2609. p. 012021#pg5> For invertible matrices, a decomposition along two binary interval trees aggregates these minors by matrix multiplication; a Boolean border of constant size handles the remaining ranks <ref:2609. p. 012021#pg6>
Graph Algorithm Efficiency
The combinatorial application is the shortest even directed-cycle problem <ref:2609.12021#pg3>, and Theorem 1. p. 12 states that for a simple directed graph on n vertices, a randomized algorithm computes the shortest even-cycle length and the union of the arc sets of all shortest even cycles in Oe(nτ+1) bit operations <ref:2609. p. 112021#pg7> Theorem 1. p. 13 provides an actual shortest cycle with worst-case running time Oe(n4) that outputs a shortest even directed cycle with probability 1 − O(n − 3) whenever one exists <ref:2609. p. 112021#pg8>
Algebraic Mechanism and Bounds
The algebraic mechanism involves the inversion count of a permutation being its oddness indicator <ref:2609.12021#pg4>, and expanding this count gives a sum of products of two entries and a complementary determinant <ref:2609. p. 112021#pg5> The evaluation of these traces with the smaller output dimension and summing over all scales costs O(nτ) <ref:2609. p. 112021#pg12> Proposition 4. p. 52 states that the value Φ(A) of any n × n matrix over any characteristic-two field can be computed deterministically in O(nτ) field operations <ref:2609. p. 512021#pg3>
Witness Extraction Techniques
The paper presents three methods for extracting a shortest even cycle, including exact maintenance which provides a general fourth-degree bound and the stronger parameter bounds in Appendix A <ref:2609.12021#pg2> Method A. p. 11 involves querying whether a subgraph contains an l-cycle using Lemma 7. p. 31 to find an arc set of size l <ref:2609. p. 712021#pg4> Method A. p. 12 involves vertex deletion rounds, and Proposition A. p. 93 provides a combined parameter bound for returning a shortest even cycle with probability 1 − O(n − 3) <ref:2609. p. 012021#pg5> The algorithm can use O(n 3) field elements; quadratic space is separately available for Proposition A. p. 13 <ref:2609. p. 012021#pg5>
Relation to Earlier Work
The paper notes that the parity cycle-cover polynomial and its relation to the permanent and determinant originate in the framework of Vazirani and Yannakakis [VY89] <ref:2609.12021#pg9> The authors use this proportional-row expansion and do not claim it as a new combinatorial device <ref:2609. p. 212021#pg10> The result is a uniform matrix multiplication bound over every characteristic-two field, including all singular inputs <ref:2609. p. 212021#pg2> All fast bounds include the rank, inverse, interpolation, and polynomial arithmetic costs <ref:2609. p. 012021#pg5> The scalar and gradient algorithms can use quadratic workspace; direct truncated-series extraction can require cubic workspace <ref:2609. p. 112021#pg3> The paper's organization is structured with Section 2 giving notation and algebraic tools <ref:2609.12021#pg2> Sections 3–5 prove Theorem 1. p. 21 <ref:2609. p. 012021#pg3>, Section 6 proves the graph length, support, and uniqueness results <ref:2609. p. 212021#pg2>, Section 7 gives the general witness algorithm, and Appendix A proves the parameter bounds <ref:2609. p. 212021#pg3> The references listed include [BH74] James R. p. 2 Bunch and John E. p. 2 Hopcroft <ref:2609. p. 012021#pg5> [BHK24] Andreas Björklund, Thore Husfeldt, and Petteri Kaski <ref:2609. p. 112021#pg5> [BHL17] Andreas Björklund, Thore Husfeldt, and Isak Lyckberg <ref:2609. p. 212021#pg5> [BKK14] Andreas Björklund, Petteri Kaski, and Łukasz Kowalik <ref:2609. p. 012021#pg5> [BKR09] Mark Braverman, Raghav Kulkarni, and Sambuddha Roy <ref:2609. p. 212021#pg5> [BS83] Walter Baur and Volker Strassen <ref:2609. p. 212021#pg5> [CK91] David G. Cantor and Erich Kaltofen <ref:2609. p. 012021#pg5> [DJ21] Samir Datta and Kishlaya Jaiswal <ref:2609. p. 212021#pg5> [HJ13] Roger A. p. 2 Horn and Charles R. Johnson <ref:2609. p. 012021#pg3> [JPS13] Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann <ref:2609. p. 212021#pg5> [LN97] Rudolf Lidl and Harald Niederreiter <ref:2609. p. 012021#pg5> [McC04] William McCuaig <ref:2609. p. 112021#pg5> [RST99] Neil Robertson, Paul D. p. 1 Seymour, and Robin Thomas <ref:2609. p. 112021#pg5> [Sch80] Jacob T. p. 3 Schwartz <ref:2609. p. 012021#pg5> [Sho90] Victor Shoup <ref:2609. p. 012021#pg5> [Str69] Volker Strassen <ref:2609. p. 012021#pg5> [Val79] Leslie G. p. 2 Valiant <ref:2609. p. 012021#pg5> [VY89] Vijay V. p. 2 Vazirani and Mihalis Yannakakis <ref:2609. p. 212021#pg5> [vzGG13] Joachim von zur Gathen and Jürgen Gerhard <ref:2609. p. 012021#pg5> [Zip79] Richard Zippel <ref:2609. p. 3
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Fast evaluation of odd-permutation sums can be performed deterministically in O(n tau) field operations for any n x n matrix over a field of characteristic two, which allows for the computation of Φ(A) and all its first partial derivatives G(A). This capability extends to singular matrices and the binary field.
-
The shortest even directed cycle length can be computed in Oe(n tau+1) bit operations with high probability, improving the previous O(n tau+3) bound, which is essential for real-time graph analysis of weighted adjacency matrices.
-
Exact maintenance of a nonzero coefficient allows for the output of a shortest even cycle with high probability in O(n 4) time for general graphs, providing a practical witness algorithm to find cycles that omit few vertices.
-
The system can deterministically output the shortest even cycle under the promise that an even cycle, if present, has a unique shortest member by setting every arc weight to one, providing a deterministic guarantee for specific graph structures.
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time