From the 1 of 34 linked papers with an AI index.
1 citations · 1 across the 13 of their papers we have counts for
11 papers · 1 filter
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…
Strong Inapproximability for a Promise Rank Problem
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
Given a linear subspace of matrices over that is promised to contain a matrix of rank , we prove that it is hard to find a matrix of rank $n^{o(1/…
Classification of Non-redundancy of Boolean Predicates of Arity 4
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Given a constraint satisfaction problem (CSP) predicate , the non-redundancy (NRD) of is maximum-sized instance on variables such that for every clause of…
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some such that given as input a -CSP ins…
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of circui…
PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
Venkatesan Guruswami, Xuandi Ren, Kewen Wu
The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring on…