Satisfying more than half of a system of linear equations over GF(2): a multivariate approach

DOI10.1016/j.jcss.2013.10.002zbMath1285.68053OpenAlexW2020545181WikidataQ57359600 ScholiaQ57359600MaRDI QIDQ2637641

Yanyan Li

Publication date: 13 February 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/15690

zbMATH Keywords

kernelfixed-parameter tractable\textsc{MaxLin}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Unnamed Item, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Linear kernels and linear-time algorithms for finding large cuts, Large Independent Sets in Triangle-Free Planar Graphs, Polynomial kernels for vertex cover parameterized by small degree modulators, Parameterizations of test cover with bounded test sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of MaxSat above average
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• 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
• Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
• Pseudo-Boolean optimization
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• The size of the largest bipartite subgraphs
• Note on maximal bisection above tight lower bound
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• On some extremal problems in graph theory
• Parametrized complexity theory.
• Combinatorial optimization. Theory and applications.
• Max-Cut Parameterized above the Edwards-Erdős Bound
• Improved Parameterized Algorithms for above Average Constraint Satisfaction
• Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams
• Algorithms with large domination ratio
• Maximum Balanced Subgraph Problem Parameterized above Lower Bound
• Bisections above Tight Lower Bounds
• Some optimal inapproximability results
• On the advantage over a random assignment