Skip to main content

9 Result(s)

within Madhur Tulsiani Remove this filter

and

  1. No Access

    Chapter and Conference Paper

    The Complexity of Somewhat Approximation Resistant Predicates

    A boolean predicate f:{0,1} k  → {0,1} is said to be somewhat approximation resistant if for some constant ...

    Subhash Khot, Madhur Tulsiani, Pratik Worah in Automata, Languages, and Programming (2014)

  2. No Access

    Chapter and Conference Paper

    Linear Programming Hierarchies Suffice for Directed Steiner Tree

    We demonstrate that ℓ rounds of the Sherali-Adams hierarchy and 2ℓ rounds of the Lovász-Schrijver hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in ℓ-layer...

    Zachary Friggstad, Jochen Könemann… in Integer Programming and Combinatorial Opti… (2014)

  3. No Access

    Chapter and Conference Paper

    Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications

    We give new and simple combinatorial proofs of almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [7], whose almost-periodicity lemma has had far-reaching implica...

    Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani… in Automata, Languages, and Programming (2014)

  4. No Access

    Chapter and Conference Paper

    Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs

    Given a two-player one-round game G with value val(G) = (1 − η), how quickly does the value decay under parallel repetition? If G is a projection game, then it is known that we can guarantee val(G ...

    Madhur Tulsiani, John Wright, Yuan Zhou in Automata, Languages, and Programming (2014)

  5. No Access

    Chapter

    Convex Relaxations and Integrality Gaps

    We discuss the effectiveness of linear and semidefinite relaxations in approximating the optimum for combinatorial optimization problems. Various hierarchies of these relaxations, such as the ones defined by L...

    Eden Chlamtac, Madhur Tulsiani in Handbook on Semidefinite, Conic and Polyno… (2012)

  6. No Access

    Chapter and Conference Paper

    SDP Gaps for 2-to-1 and Other Label-Cover Variants

    In this paper we present semidefinite programming (SDP) gap instances for the following variants of the Label-Cover problem, closely related to the Unique Games Conjecture: (i) 2-to-1 Label-Cover; (ii) 2-to-2 ...

    Venkatesan Guruswami, Subhash Khot, Ryan O’Donnell… in Automata, Languages and Programming (2010)

  7. No Access

    Chapter and Conference Paper

    Improved Pseudorandom Generators for Depth 2 Circuits

    We prove the existence of a poly(n,m)-time computable pseudorandom generator which “1/poly(n,m)-fools” DNFs with n variables and m terms, and has seed length O(log2 nm ·loglognm). Previously, the ...

    Anindya De, Omid Etesami, Luca Trevisan… in Approximation, Randomization, and Combinat… (2010)

  8. Chapter and Conference Paper

    Time Space Tradeoffs for Attacks against One-Way Functions and PRGs

    We study time space tradeoffs in the complexity of attacks against one-way functions and pseudorandom generators.

    Anindya De, Luca Trevisan, Madhur Tulsiani in Advances in Cryptology – CRYPTO 2010 (2010)

    Download PDF (288 KB)

  9. No Access

    Chapter and Conference Paper

    Optimal Sherali-Adams Gaps from Pairwise Independence

    This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by P contains the support of a balanced pairwise i...

    Konstantinos Georgiou, Avner Magen… in Approximation, Randomization, and Combinat… (2009)