scientific article; zbMATH DE number 7650072

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.5MaRDI QIDQ5875456

Runzhou Tao, Venkatesan Guruswami

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1811.04607

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Fourier analysislower boundsCSPcommunication complexitystreaming algorithmsunique games

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Near-optimal algorithms for unique games
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• On the power of unique 2-prover 1-round games
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
• Analysis of Boolean Functions
• An optimal space lower bound for approximating MAX-CUT
• Towards a proof of the 2-to-1 games conjecture?
• On non-optimally expanding sets in Grassmann graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Streaming Lower Bounds for Approximating MAX-CUT
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

This page was built for publication: