Streaming approximation resistance of every ordering CSP
From MaRDI portal
Publication:6581871
DOI10.1007/S00037-024-00252-5zbMATH Open1542.6825MaRDI QIDQ6581871FDOQ6581871
Authors: Noah Singer, Madhu Sudan, Santhoshini Velusamy 
Publication date: 1 August 2024
Published in: Computational Complexity (Search for Journal in Brave)
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
Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)
Cites Work
- Reducibility among combinatorial problems
- Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
- On the power of unique 2-prover 1-round games
- Total Ordering Problem
- Beating the random ordering is hard: every ordering CSP is approximation resistant
- A Geometric Approach to Betweenness
- UG-hardness to NP-hardness by losing half
- Sketching cuts in graphs and hypergraphs
- Streaming Lower Bounds for Approximating MAX-CUT
- The streaming complexity of cycle counting, sorting by reversals, and other problems
- On the NP-hardness of approximating ordering-constraint satisfaction problems
- \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
- Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
- Streaming approximation resistance of every ordering CSP
- Vertex Ordering Problems in Directed Graph Streams
- An optimal space lower bound for approximating MAX-CUT
- Streaming complexity of CSPs with randomly ordered constraints
- Streaming and sketching complexity of CSPs: a survey (invited talk)
- Sketching approximability of (weak) monarchy predicates
Cited In (1)
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)
