Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
DOI10.1016/J.JCSS.2013.10.002zbMATH Open1285.68053DBLPjournals/jcss/CrowstonFGJKRRTY14OpenAlexW2020545181WikidataQ57359600 ScholiaQ57359600MaRDI QIDQ2637641FDOQ2637641
Authors: 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
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
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)
Cites Work
- Graph theory
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- Parametrized complexity theory.
- Max-Cut parameterized above the Edwards-Erdős bound
- Hitting forbidden minors: approximation and kernelization
- Incompressibility through Colors and IDs
- Some optimal inapproximability results
- Title not available (Why is that?)
- Solving MAX-\(r\)-SAT above a tight lower bound
- Pseudo-Boolean optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On some extremal problems in graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Cross-composition: a new technique for kernelization lower bounds
- Reflections on multivariate algorithmics and problem parameterization
- Combinatorial optimization. Theory and applications.
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Note on maximal bisection above tight lower bound
- Improved parameterized algorithms for above average constraint satisfaction
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized 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
- Note on Max Lin-2 above average
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- A faster fixed-parameter approach to drawing binary tanglegrams
- The size of the largest bipartite subgraphs
- Algorithms with large domination ratio
- Maximum balanced subgraph problem parameterized above lower bound
- Bisections above Tight Lower Bounds
- On the advantage over a random assignment
Cited In (12)
- Parameterizations of test cover with bounded test sizes
- Note on Max Lin-2 above average
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Linear kernels and linear-time algorithms for finding large cuts
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Solving linear equations parameterized by Hamming weight
- 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)
