Systems of linear equations over F₂ and problems parameterized above average

DOI10.1007/978-3-642-13731-0_17MaRDI QIDQ3569888zbMATH OpenOpenAlexFDO

Authors

Publication date 22 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13731-0_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Note on Max Lin-2 above average
• 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\)
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach

Cited in

(20)

• Note on maximal bisection above tight lower bound
• Betweenness parameterized above tight lower bound
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Improved parameterized algorithms for above average constraint satisfaction
• Kernelization -- preprocessing with a guarantee
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Solving linear equations parameterized by Hamming weight
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Solving linear equations parameterized by Hamming weight
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Confronting intractability via parameters
• Parameterized constraint satisfaction problems: a survey
• A probabilistic approach to problems parameterized above or below tight bounds
• Solving MAX-\(r\)-SAT above a tight lower bound
• Note on Max Lin-2 above average
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• An asymptotic version of Dumnicki's algorithm for linear systems in \({\mathbb{CP}^2}\)

This page was built for publication: Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569888)