Search by Category

A

• algorithms (20)
• all-pairs shortest paths (1)
• approximation algorithms (16)
• arithmetic circuits (2)
• arithmetic formulas (1)
• Arthur (1)
• average case (2)

B

• Boolean formulas (5)
• Boolean functions (1)
• bottleneck paths (1)
• branching programs (2)

C

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

D

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

E

• electronic commerce (2)
• entanglement (1)
• error-correcting codes (1)
• expanders (5)
• explicit construction (3)
• extractors (1)

F

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

G

• game theory (1)
• game tree (1)
• games (1)
• geometric algorithms (1)
• Gowers norm (2)
• graduate survey (1)
• graph algorithms (1)
• graphs (6)
• Grothendieck inequality (1)

H

• Hamming distance (1)
• hypergraphs (1)

I

• inapproximability (4)
• influence (1)
• integrality gap (3)
• interactive proofs (1)

L

• lattice algorithms (1)
• learning (3)
• linear threshold function (1)
• low degree (1)
• lower bounds (18)
• LP relaxation (1)

M

• matrix multiplication (1)
• matrix multiplication over semirings (1)
• matrix rigidity (1)
• max-cut (1)
• Merlin (1)
• metric embedding (2)
• multiparty communication complexity (1)

N

• NAND tree (1)
• networks (6)
• norm (1)
• note (2)
• number theory (1)

O

• online algorithms (2)

P

• PAC learning (1)
• parallel repetition (1)
• PCP (5)
• polynomial time approximation scheme (1)
• polynomial-time hierarchy (1)
• polynomials (4)
• probabilistically checkable proof (1)
• probabilistically checkable proofs (5)
• proof complexity (3)
• property testing (4)
• pseudorandom (1)

Q

• quadratic programming (1)
• quantum (14)
• quantum information (1)
• quantum walk (2)
• query complexity (7)

R

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

S

• SAT (4)
• SDP gap (1)
• search (1)
• secret sharing (1)
• security (1)
• semidefinite programming (2)
• separation of complexity classes (1)
• short (12)
• shortest paths (1)

T

• traveling salesman (2)

U

• UGC-hardness (1)
• unique games (2)

V

• voting (1)

W

• write-once memory (1)