
Linear Space Streaming Lower Bounds for Approximating CSPs
We consider the approximability of constraint satisfaction problems in t...
read it

Streaming approximation resistance of every ordering CSP
An ordering constraint satisfaction problem (OCSP) is given by a positiv...
read it

Approximability of all finite CSPs in the dynamic streaming setting
A constraint satisfaction problem (CSP), MaxCSP( F), is specified by a ...
read it

Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), MaxCSP(f), is a maximi...
read it

Optimal Streaming Approximations for all Boolean Max2CSPs
We prove tight upper and lower bounds on approximation ratios of all Boo...
read it

Simple, Credible, and ApproximatelyOptimal Auctions
We identify the first static credible mechanism for multiitem additive ...
read it
Santhoshini Velusamy
is this you? claim profile