|
|
Rigidity |
|||||||||||||||||
Deterministic approximation algorithms for the nearest codeword problem
Circuit Lower Bounds, Help Functions, and the Remote Point Problem
More on Average Case vs Approximation Complexity
Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity
| ||||||||||||||||||
|
|
Lower Bounds for Arithmetic Circuits |
|||||||||||||||||
Non-commutative circuits and the sum-of-squares problem
Elusive Functions and Lower Bounds for Arithmetic Circuits
Lower Bounds on Arithmetic Circuits via Partial Derivatives
On the Complexity of Matrix Product'
| ||||||||||||||||||
|
|
Locally Correctable Codes |
|||||||||||||
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
Tight lower bounds for 2-query LCCs over finite fields
On the efficiency of local decoding procedures for error-correcting codes.
| ||||||||||||||
|
|
Graph Isomorphism |
|||||||||||||
Faster Isomorphism Testing of Strongly Regular Graphs
An optimal lower bound on the number of variables for graph identifications
Isomorphism of graphs of bounded valence can be tested in polynomial time
| ||||||||||||||
|
|
3-Coloring |
|||||||||||||
New Approximation Algorithms for Graph Coloring
Approximate graph coloring by semidefinite programming
On the hardness of 4-coloring a 3-colorable graph
| ||||||||||||||
|
|
Communication Complexity |
|||||||||||||||||
On Rank vs. Communication Complexity
Complexity Measures and Decision Tree Complexity: A Survey
Towards deterministic tree code constructions
The multiparty communication complexity of set disjointness
| ||||||||||||||||||
|
|
Computations over Composites |
|||||||||||||||||
On ACC
Non-Uniform ACC Circuit Lower Bounds
A lower bound on the mod 6 degree of the OR function
Linear Systems over Composite Moduli
| ||||||||||||||||||
|
|
Analysis of Boolean functions |
|||||||||||
Boolean functions with small spectral norm
An O(n^log log n) learning algorithm for DNF under the uniform distribution
| ||||||||||||