Streaming approximation resistance of every ordering CSP

DOI10.1007/S00037-024-00252-5MaRDI QIDQ6581871zbMATH OpenFDO

Authors Noah Singer, Madhu Sudan, Santhoshini Velusamy

Publication date 1 August 2024

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00037-024-00252-5

zbMATH Keywords

approximation resistanceconstraint satisfaction problemsordering constraintsstreaming algorithms

Mathematics Subject Classification ID

Computational aspects of satisfiability (68R07) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Streaming approximation resistance of every ordering CSP
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Approximating Bounded Occurrence Ordering CSPs

Cites work

• (1 + (1))-approximation to MAX-CUT requires linear space
• A Geometric Approach to Betweenness
• An optimal space lower bound for approximating MAX-CUT
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• On the power of unique 2-prover 1-round games
• Reducibility among combinatorial problems
• Sketching approximability of (weak) monarchy predicates
• Sketching cuts in graphs and hypergraphs
• Streaming and sketching complexity of CSPs: a survey (invited talk)
• Streaming approximation resistance of every ordering CSP
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Streaming complexity of CSPs with randomly ordered constraints
• Streaming Lower Bounds for Approximating MAX-CUT
• The streaming complexity of cycle counting, sorting by reversals, and other problems
• Total Ordering Problem
• UG-hardness to NP-hardness by losing half
• Vertex Ordering Problems in Directed Graph Streams

Cited in

(1)

• Streaming approximation resistance of every ordering CSP

This page was built for publication: Streaming approximation resistance of every ordering CSP

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