2026-08-07T13:42:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18840 2024-03-06T11:02:42Z ddc:004 open_access

Oblivious Algorithms for the Max-kAND Problem Singer, Noah G. streaming algorithm approximation algorithm constraint satisfaction problem (CSP) factor-revealing linear program Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-kAND problem. This is a class of simple, combinatorial algorithms which round each variable with probability depending only on a quantity called the variable’s bias. Our definition generalizes a class of algorithms defined by Feige and Jozeph (Algorithmica '15) for Max-DICUT, a special case of Max-2AND. For each oblivious algorithm, we design a so-called factor-revealing linear program (LP) which captures its worst-case instance, generalizing one of Feige and Jozeph for Max-DICUT. Then, departing from their work, we perform a fully explicit analysis of these (infinitely many!) LPs. In particular, we show that for all k, oblivious algorithms for Max-kAND provably outperform a special subclass of algorithms we call "superoblivious" algorithms. Our result has implications for streaming algorithms: Generalizing the result for Max-DICUT of Saxena, Singer, Sudan, and Velusamy (SODA'23), we prove that certain separation results hold between streaming models for infinitely many CSPs: for every k, O(log n)-space sketching algorithms for Max-kAND known to be optimal in o(√n)-space can be beaten in (a) O(log n)-space under a random-ordering assumption, and (b) O(n^{1-1/k} D^{1/k}) space under a maximum-degree-D assumption. Even in the previously-known case of Max-DICUT, our analytic proof gives a fuller, computer-free picture of these separation results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah G. Singer 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.15 urn:nbn:de:0030-drops-188409 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.15 eng https://creativecommons.org/licenses/by/4.0/legalcode