Search by Category

A

• algorithms (18)
• approximation algorithms (15)
• arithmetic circuits (2)
• arithmetic formulas (1)
• average case (2)

B

• Boolean formulas (4)
• Boolean functions (1)
• branching programs (2)

C

• Cayley graphs (2)
• circuit complexity (1)
• circuits (3)
• clustering (2)
• CNF-DNF formulas (4)
• combinatorial optimization (5)
• comment (1)
• comment added (1)
• communication complexity (6)
• communication security (1)
• complexity classes (4)
• complexity theory (21)
• concentration inequalities (1)
• constraint satisfaction (1)

D

• data stream (1)
• degree-d norm (1)
• derandomization (2)
• distributed computing (1)

E

• electronic commerce (2)
• error-correcting codes (1)
• expanders (4)
• extractors (1)

F

• fault tolerance (1)
• flows (1)
• formulas (5)
• Fourier analysis (1)
• Fourier transform (2)

G

• game theory (1)
• game tree (1)
• geometric algorithms (1)
• graduate survey (1)
• graphs (5)

H

• Hamming distance (1)
• hypergraphs (1)

I

• inapproximability (3)
• influence (1)
• integrality gap (2)

L

• lattice algorithms (1)
• learning (3)
• lower bounds (16)
• LP relaxation (1)

M

• matrix rigidity (1)
• metric embedding (1)
• multiparty communication complexity (1)

N

• NAND tree (1)
• networks (6)
• number theory (1)

O

• online algorithms (2)

P

• PAC learning (1)
• polynomial time approximation scheme (1)
• polynomial-time hierarchy (1)
• polynomials (3)
• probabilistically checkable proofs (3)
• proof complexity (3)
• property testing (3)

Q

• quantum (10)
• quantum walk (1)
• query complexity (6)

R

• random sampling (3)
• rank (1)
• resource allocation (1)
• routing (2)

S

• search (1)
• secret sharing (1)
• separation of complexity classes (1)
• short (10)

T

• traveling salesman (2)

U

• unique games (1)