Does subset sum admit short proofs?
From MaRDI portal
Cites work
- A completeness theory for polynomial (Turing) kernelization
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph
- A near-linear pseudopolynomial time algorithm for subset sum
- A near-optimal planarization algorithm
- A subquadratic approximation scheme for partition
- Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
- An exponential time parameterized algorithm for planar disjoint paths
- An introduction to abstract algebra
- AND-compression of NP-complete problems: streamlined proof and minor observations
- Approximating Pathwidth for Graphs of Small Treewidth
- Carathéodory bounds for integer cones
- Collaborating with Hans: Some Remaining Wonderments
- Computational Complexity
- Coverability in VASS revisited: improving Rackoff's bound to obtain conditional optimality
- Dense subset sum may be the hardest
- Efficient cryptographic schemes provably as secure as subset sum
- Exponential time paradigms through the polynomial time lens
- Fast and simple modular subset sum
- Fast modular subset sum using linear sketching
- Faster minimization of tardy processing time on a single machine
- Faster Pseudopolynomial Time Algorithms for Subset Sum
- Finding k Disjoint Paths in a Directed Planar Graph
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Graph minors. XX: Wagner's conjecture
- Hiding information and signatures in trapdoor knapsacks
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 5139161 (Why is no real title available?)
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 2080216 (Why is no real title available?)
- scientific article; zbMATH DE number 7740931 (Why is no real title available?)
- scientific article; zbMATH DE number 7788444 (Why is no real title available?)
- scientific article; zbMATH DE number 7788445 (Why is no real title available?)
- scientific article; zbMATH DE number 7788446 (Why is no real title available?)
- Hypergraphic degree sequences are hard
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
- Kernelization lower bounds through colors and IDs
- Kernelization. Theory of parameterized preprocessing
- Knapsack and subset sum with small items
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- Logical foundations of proof complexity
- Measuring the problem-relevant information in input
- Minimizing tardy processing time on a single machine in near-linear time
- Modular subset sum, dynamic strings, and zero-sum sets
- New generic algorithms for hard knapsacks
- Nondeterministic direct product reductions and the success probability of SAT solvers
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On integer programming and convolution
- On Landau's function g(n)
- On minimizing tardy processing time, Max-Min skewed convolution, and triangular structured ILPs
- On problems equivalent to \((\min,+)\)-convolution
- On space efficiency of algorithms working on structural decompositions of graphs
- On the complexity of circuit satisfiability
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On the Hardness of Compressing Weights
- On the space and circuit complexity of parameterized problems: classes and completeness
- Online algorithms with advice: the tape model
- Parameterized algorithms
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Parameterized proof complexity
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
- PRIMES is in P
- Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
- Reducing a target interval to a few exact queries
- Satisfiability certificates verifiable in subexponential time
- Scheduling lower bounds via and subset sum
- SETH-based Lower Bounds for Subset Sum and Bicriteria Path
- Solving low-density subset sum problems
- The design of approximation algorithms
- The directed subgraph homeomorphism problem
- The disjoint paths problem in quadratic time
- The Graver complexity of integer programming
- The parameterised complexity of integer multicommodity flow
- The relative efficiency of propositional proof systems
- Width-parametrized SAT: time-space tradeoffs
- XNLP-completeness for parameterized problems on graphs with a linear structure
This page was built for publication: Does subset sum admit short proofs?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260680)
