14 citations · 27 across the 20 of their papers we have counts for
24 papers
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Yinhao Dong, Pan Peng, Ali Vakilian +2
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algori…
Cores Characterize the One-Pass Streaming Complexity of CSPs
Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1
We study the one-pass streaming complexity of CSPs over a fixed finite relation under three natural objectives: , deciding whether all constraints can be satis…
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Amatya Sharma, Santhoshini Velusamy
Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems () that governs kerneli…
Characterizing Streaming Decidability of CSPs via Non-Redundancy
Amatya Sharma, Santhoshini Velusamy
We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language , that is, a fin…
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
For an arbitrary family of predicates and any , we prove a single-pass, linear-space streaming lower bound against the gap promise pro…
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
Santhoshini Velusamy
The Max-DICUT problem has gained a lot of attention in the streaming setting in recent years, and has so far served as a canonical problem for designing algorithms for general cons…
Sketching approximations and LP approximations for finite CSPs are related
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
We identify a connection between the approximability of CSPs in two models: (i) sublinear space streaming algorithms, and (ii) the basic LP relaxation. We show that whenever the ba…
Optimally detecting uniformly-distributed heavy hitters in data streams
Santhoshini Velusamy, Huacheng Yu
Given a stream of items from a Universe of size poly, and a parameter , an item is said to be an heavy hitter if its frequency $…
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al…
Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
Samuel Hwang, Noah G. Singer, Santhoshini Velusamy
In the maximum directed cut problem, the input is a directed graph , and the goal is to pick a partition of the vertices such that as many edg…
On the size of maximum cut in planar graphs
Pranay Gorantla, Santhoshini Velusamy
We show that the size of maximum cut in a planar graph with edges is at least . We also show that maximal planar graphs saturate this bound.
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We give an -space single-pass -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on …
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of matroids. The best-known algorithms achieve a -approximation, even when r…
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan +1
We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\…
Sketching Approximability of (Weak) Monarchy Predicates
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi +2
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals.…
Fair allocation of a multiset of indivisible items
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
We study the problem of fairly allocating a multiset of indivisible items among agents with additive valuations. Specifically, we introduce a parameter for the numb…
On sketching approximations for symmetric Boolean CSPs
Joanna Boyland, Michael Hwang, Tarun Prasad +2
A Boolean maximum constraint satisfaction problem, Max-CSP(), is specified by a predicate . An -variable instance of Max-CSP() consists of a list o…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
Streaming approximation resistance of every ordering CSP
Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
An ordering constraint satisfaction problem (OCSP) is defined by a family of predicates mapping permutations on to . An instance of Max-OCSP…
Sketching approximability of all finite CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
A constraint satisfaction problem (CSP), , is specified by a finite set of constraints for positive int…
Approximability of all Boolean CSPs with linear sketches
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
In this work we consider the approximability of in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Sp…
Elementary analysis of isolated zeroes of a polynomial system
Mitali Bafna, Madhu Sudan, Santhoshini Velusamy +1
Wooley ({\em J. Number Theory}, 1996) gave an elementary proof of a Bezout like theorem allowing one to count the number of isolated integer roots of a system of polynomial equatio…
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an…
Multi-item Non-truthful Auctions Achieve Good Revenue
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier +2
We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions, which applies to both truthful and non-truthful auctions. Gi…