Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
From MaRDI portal
Publication:2637641
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)
Recommendations
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Note on Max Lin-2 above average
- Parameterized constraint satisfaction problems: a survey
Cites work
- scientific article; zbMATH DE number 3510345 (Why is no real title available?)
- scientific article; zbMATH DE number 1096865 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- scientific article; zbMATH DE number 5485570 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A faster fixed-parameter approach to drawing binary tanglegrams
- A probabilistic approach to problems parameterized above or below tight bounds
- Algorithms with large domination ratio
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- Bisections above Tight Lower Bounds
- Combinatorial optimization. Theory and applications.
- Cross-composition: a new technique for kernelization lower bounds
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Graph theory
- Hitting forbidden minors: approximation and kernelization
- Improved parameterized algorithms for above average constraint satisfaction
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Max-Cut parameterized above the Edwards-Erdős bound
- Maximum balanced subgraph problem parameterized above lower bound
- Note on Max Lin-2 above average
- Note on maximal bisection above tight lower bound
- On problems without polynomial kernels
- On some extremal problems in graph theory
- On the advantage over a random assignment
- Parameterizing above or below guaranteed values
- Parametrized complexity theory.
- Pseudo-Boolean optimization
- Reflections on multivariate algorithmics and problem parameterization
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Solving MAX-\(r\)-SAT above a tight lower bound
- Some optimal inapproximability results
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- The size of the largest bipartite subgraphs
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
Cited in
(12)- Parameterizations of test cover with bounded test sizes
- Note on Max Lin-2 above average
- Linear kernels and linear-time algorithms for finding large cuts
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Solving linear equations parameterized by Hamming weight
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Large independent sets in triangle-free planar graphs
- Solving linear equations parameterized by Hamming weight
- Parameterized constraint satisfaction problems: a survey
This page was built for publication: Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637641)
