Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
From MaRDI portal
Publication:2637641
DOI10.1016/j.jcss.2013.10.002zbMath1285.68053WikidataQ57359600 ScholiaQ57359600MaRDI QIDQ2637641
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
15A60: Norms of matrices, numerical range, applications of functional analysis to matrix theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Large Independent Sets in Triangle-Free Planar Graphs, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Parameterizations of test cover with bounded test sizes, Linear kernels and linear-time algorithms for finding large cuts, Polynomial kernels for vertex cover parameterized by small degree modulators
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
