Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with expander:
TR06-105 | 23rd August 2006
Avi Wigderson, David Xiao

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

TR09-007 | 9th January 2009
Eli Ben-Sasson, Michael Viderman

Tensor Products of Weakly Smooth Codes are Robust

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, ... more >>>

TR09-021 | 2nd March 2009
Konstantin Makarychev, Yury Makarychev

How to Play Unique Games on Expanders

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>

TR12-141 | 22nd October 2012
Dmitry Itsykson, Dmitry Sokolov

Lower bounds for myopic DPLL algorithms with a cut heuristic

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

TR14-093 | 22nd July 2014
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Resolution complexity of perfect mathcing principles for sparse graphs

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

TR16-129 | 16th August 2016
Emanuele Viola, Avi Wigderson

Local Expanders

Revisions: 1

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

TR22-083 | 2nd June 2022
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Hardness of Maximum Likelihood Learning of DPPs

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fitted to match the data; typically, we ... more >>>

ISSN 1433-8092 | Imprint