scientific article; zbMATH DE number 7561747
From MaRDI portal
Publication:5092469
Recommendations
- On the Computational Complexity of Modular Symbols
- Hardness and optimality in QBF proof systems modulo NP
- On the bit complexity of sum-of-squares proofs
- On the complexity of solving linear congruences and computing nullspaces modulo a constant
- Semi-algebraic complexity of quotients and sign determination of remainders
- On the Satisfiability of Modular Arithmetic Formulae
- Proof complexity modulo the polynomial hierarchy: understanding alternation as a source of hardness
- Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
- An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial
- On the modulo degree complexity of Boolean functions
Cites work
- 2-D Tucker is PPA complete
- A Sperner lemma complete for PPA
- Adventures in monotone complexity and TFNP
- Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
- Bisection of Circle Colorings
- Consensus halving is PPA-complete
- Counting classes: Thresholds, parity, mods, and fewness
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- How easy is local search?
- scientific article; zbMATH DE number 1114015 (Why is no real title available?)
- scientific article; zbMATH DE number 6783433 (Why is no real title available?)
- Integer factoring and modular square roots
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- On a Topological Generalization of a Theorem of Tverberg
- On Kemnitz' conjecture concerning lattice-points in the plane
- On the complexity of the parity argument and other inefficient proofs of existence
- On the polynomial parity argument complexity of the combinatorial Nullstellensatz
- On total functions, existence theorems and computational complexity
- Propositional proofs and reductions between NP search problems
- Regular subgraphs of almost regular graphs
- Splitting necklaces
- Sum-of-squares meets Nash: lower bounds for finding any equilibrium
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- The complexity of computing a Nash equilibrium
- The complexity of splitting necklaces and bisecting ham sandwiches
- The relative complexity of NP search problems
- Understanding PPA-completeness
- White-box vs. black-box complexity of search problems: Ramsey and graph property testing
Cited in
(8)- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Consensus Halving for Sets of Items
- Consensus-Halving: Does It Ever Get Easier?
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Intersection classes in TFNP and proof complexity
- TFNP intersections through the Lens of feasible disjunction
- The chromatic number of Kneser hypergraphs via consensus division
- The chromatic number of Kneser hypergraphs via consensus division
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092469)
