Search by Category
3
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Z
3
A
- ABPs (1)
- Absolute value variation (1)
- Acyclic subgraph (1)
- Adaptive (1)
- Additive combinatorics (5)
- Affine-invariant codes (3)
- Agreement testing (1)
- Algebraic algorithms (1)
- Algebraic circuits (1)
- Algebraic complexity (14)
- Algebraic dependence (1)
- Algebraic geometry (1)
- Algebraic proof systems (1)
- Algebraic-geometric codes (1)
- Algorithmic game theory (4)
- Algorithms (86)
- All pairs max flow (1)
- All-pairs shortest paths (1)
- AND-OR tree (1)
- Anti-concentration (1)
- APPROX (22)
- APPROX-RANDOM 2012 special issue (9)
- APPROX-RANDOM 2013 special issue (7)
- APPROX-RANDOM 2014 special issue (5)
- APPROX-RANDOM 2015 special issue (6)
- APPROX-RANDOM 2016 special issue (4)
- APPROX-RANDOM 2019 special issue (7)
- Approximate degree (3)
- Approximate polynomial (1)
- Approximation (4)
- Approximation algorithms (48)
- Approximation resistance (3)
- Arithmetic branching programs (1)
- Arithmetic circuits (15)
- Arithmetic complexity (1)
- Arithmetic formulas (3)
- Arthur (3)
- Arthur-Merlin (2)
- Auction (1)
- Average case (6)
- Average sensitivity (1)
B
- Balanced allocations (1)
- Belief propagation (1)
- Bell inequalities (1)
- Bell inequality violation (1)
- Beyond worst-case analysis (1)
- Bilinear complexity (1)
- Biography (2)
- Bisection (1)
- Bloom filters (1)
- Boolean circuits (1)
- Boolean complexity (1)
- Boolean cube (1)
- Boolean formulas (6)
- Boolean functions (23)
- Boolean special issue (10)
- Boosting (1)
- Border rank (1)
- Boson (1)
- Bottleneck paths (1)
- Bounded independence (1)
- Bounded-depth circuits (2)
- BQP (4)
- Branching programs (8)
- Branchwidth (1)
- Broadcast scheduling (1)
- Buffer (1)
- Busy-beaver function (1)
C
- Cayley graphs (3)
- CCC (26)
- CCC 2016 special issue (6)
- CCC 2017 special issue (5)
- CCC 2018 special issue (5)
- CCC 2019 special issue (7)
- CCC 2020 special issue (3)
- Cell probe (2)
- Character sums (1)
- Chinese Remainder Theorem (1)
- Chromatic number (1)
- Circuit complexity (23)
- Circuit size (1)
- Circuit value (1)
- Circuits (6)
- Circulant (1)
- Clique (2)
- Closest Vector Problem (1)
- Clustering (5)
- CNF-DNF formulas (8)
- Co-clustering (1)
- Codes (8)
- Coding theory (1)
- Collision (2)
- Coloring (1)
- Combinatorial optimization (8)
- Combinatorics (3)
- Comment (1)
- Commented on (3)
- Communication complexity (27)
- Communication security (1)
- Commutative rank (1)
- Competing provers (1)
- Completeness (6)
- Complexity (17)
- Complexity classes (13)
- Complexity theory (162)
- Composition theorems (1)
- Compression (1)
- Computability (1)
- Computational complexity (1)
- Computational entropy (1)
- Concentration (1)
- Concentration inequalities (1)
- Conditional lower bounds (1)
- Conditional sampling (1)
- Conjunction (2)
- Connectivity (1)
- Constraint satisfaction (14)
- Constructive (1)
- Convex geometry (1)
- Convex optimization (3)
- Convex programming (1)
- Convolution (1)
- Correlated sampling (1)
- Correlation bounds (2)
- Counting (2)
- Counting -- modular (1)
- Coupling (1)
- Covering complexity (1)
- Cryptography (10)
- CSP (2)
D
- Data stream (3)
- Data structures (4)
- Davis-Putnam procedure (1)
- De Finetti theorem (1)
- Decision tree (8)
- Degree (1)
- Degree of Boolean functions (1)
- Degree-d norm (2)
- Depth-4 circuits (1)
- Derandomization (11)
- Determinant (1)
- Dichotomy (2)
- Dictatorship test (1)
- Differential equations (1)
- Differential privacy (2)
- Diffusion (1)
- Discrepancy (4)
- Discrete geometry (1)
- Disjointness (2)
- Distance transform (1)
- Distributed computing (3)
- Distribution testing (2)
- Distribution-free testing (2)
- Distributions (2)
- Dominating set (1)
- Dual polynomials (2)
- Dynamic data structures (1)
- Dynamical systems (1)
E
- Ecommerce (8)
- Edge coloring (1)
- Electronic cash (1)
- Electronic commerce (6)
- Element distinctness (1)
- Energy minimization (1)
- Entanglement (3)
- Entropy (5)
- Enumeration (1)
- Equivalence testing (1)
- Error-correcting codes (10)
- Expanders (12)
- Expansion (1)
- Explicit construction (9)
- Exponential-Time Hypothesis (1)
- EXPSPACE (1)
- Extended formulations (2)
- Extension complexity (1)
- Extractors (5)
- Extremal graph theory (1)
F
- Fault tolerance (1)
- Feedback arc set (1)
- Feedback vertex set (1)
- Field extension (2)
- Fine-grained complexity (1)
- Finite field (1)
- Fixed point (1)
- Flocking (1)
- Foreword (14)
- Formula (1)
- Formula complexity (1)
- Formula evaluation (1)
- Formulas (8)
- Formulas over the reals (1)
- Fourier analysis (16)
- Fourier transform (3)
- Frobenius automorphisms (1)
- Functional lower bounds (1)
G
- Gadget (1)
- Game theory (7)
- Game tree (1)
- Games - $d$-to-1 (1)
- Gaussian isoperimetry (2)
- Gaussian width (1)
- GCT Chasm (1)
- Geometric algorithms (1)
- Geometric intersection graphs (1)
- Geometry (1)
- Gomory-Hu (1)
- Goppa codes (1)
- Gowers norm (3)
- Graduate survey (9)
- Graph algorithms (3)
- Graph genus (1)
- Graph homomorphisms (1)
- Graph isomorphism (2)
- Graph spanners (1)
- Graph-based codes (1)
- Graphs (21)
- Graphs - Hamiltonian (1)
- Graphs - planar (1)
- Grothendieck inequality (5)
- Group (2)
- Group isomorphism (2)
H
- Hamiltonian (1)
- Hamiltonian cycle (1)
- Hamiltonian Monte Carlo (1)
- Hamming distance (4)
- Hardness amplification (1)
- Hardness of approximation (1)
- Hardness versus randomness (1)
- Harmonic analysis (1)
- Hashing (3)
- Heuristic (1)
- Hidden clique (1)
- Hidden subgroup problem (1)
- Hierarchies (1)
- High dimension (1)
- High-dimensional geometry (1)
- Hitting set (5)
- Homomorphic encryption (1)
- Homomorphism (1)
- Hopcroft's Problem (1)
- Horn-3SAT (1)
- Hybrid argument (1)
- Hypercontractivity (2)
- Hypercube (1)
- Hypergraph (1)
- Hypergraph expansion (1)
- Hypergraphs (3)
- Hypergrid (1)
I
- Image processing (1)
- Inapproximability (30)
- Inapproximatbility (1)
- Incidence geometry (1)
- Inclusion matrices (1)
- Indepedent set (1)
- Independence (1)
- Independent set (1)
- Inequalities (1)
- Inequalities for elementary symmetric polynomials (1)
- Inequality (1)
- Influence (8)
- Information complexity (2)
- Information theory (1)
- Integer program (1)
- Integrality gap (7)
- Interactive proofs (7)
- Interpolation (1)
- Interval graphs (1)
- Invariance (1)
- IPS (1)
- Irreducible polynomials (1)
- Isoperimetry (2)
J
K
- $k$-cut (1)
- $k$-way Hypergraph Cut (1)
- $k$-wise independence (3)
- K-median (1)
- K-page graph (1)
- Karchmer-Wigderson games (1)
- Knapsack (1)
- Kolomogorov complexity (1)
- Koszul flattening (1)
L
- Label cover (3)
- Label cover - smooth (1)
- Latin transversal (1)
- Lattice (3)
- Lattice algorithms (2)
- LDPC codes (1)
- Learning (10)
- Learning distributions (1)
- Learning with errors (1)
- Learning-noisy (1)
- Learning-unsupervised (1)
- Lifted codes (1)
- Linear optics (1)
- Linear probing (1)
- Linear programming (5)
- Linear programming duality (1)
- Linear programming hierarchy (1)
- Linear threshold function (1)
- Linearity testing (2)
- List-decoding (1)
- Local Hamiltonian problem (1)
- Local testing (1)
- Locality (1)
- Locality-sensitive hashing (1)
- Locally correctable codes (2)
- Locally decodable codes (1)
- Locally testable codes (6)
- Logconcave distribution (1)
- Lovász Local Lemma (1)
- Low degree (1)
- Low-degree testing (1)
- Lower bound (2)
- Lower bounds (78)
- LP relaxation (2)
M
- Machine learning (1)
- Majority (2)
- Market equilibrium (1)
- Marketing -- viral (1)
- Markets (1)
- Matchgates (1)
- Matching (2)
- Matrix multiplication (6)
- Matrix multiplication over semirings (1)
- Matrix rigidity (3)
- Matrix spaces (1)
- Max flow (2)
- Max-cut (1)
- Maximum cut (1)
- Maximum Inner Product (1)
- Means (1)
- Mechanism design (2)
- Merlin (3)
- Message passing (1)
- Metric embedding (3)
- Metric spaces (2)
- Min-convolution (1)
- Minimum bisection (1)
- Minimum circuit size (1)
- Minimum spanning tree (1)
- Monotone (1)
- Monotone circuits (2)
- Monotone complexity (1)
- Monotone formula (1)
- Monotone functions (3)
- Monotonicity (1)
- Motwani special issue (11)
- Multilinear (1)
- Multiobjective optimization (1)
- Multiparty communication complexity (5)
- Multiplication (1)
- Multiplicative weight updates (1)
N
- $n$-vector model (1)
- NAND tree (1)
- Nash equilibrium (4)
- Natural algorithms (1)
- Nearest neighbor (1)
- Necklaces (1)
- Network design (1)
- Network flow (2)
- Network games (1)
- Network testing (1)
- Networks (10)
- Networks -- social (1)
- Nilpotent group (1)
- NOF model (1)
- Noise (2)
- Noise models (1)
- Noisy computation (3)
- Noncommutative (5)
- Nondeterminism (3)
- Nondeterministic (2)
- Nonlocal games (2)
- Norm (2)
- Note (20)
- NP-completeness (2)
- NP-hardness (1)
- Number theory (1)
O
- One-way functions (2)
- Online algorithms (13)
- Online decision making (1)
- Online matching (1)
- Optics (1)
- Optimization (1)
- OSSS inequality (2)
P
- $p$-groups (1)
- PAC learning (1)
- Packing (2)
- Pairwise independence (1)
- Parallel complexity (1)
- Parallel repetition (1)
- Parametrized complexity (1)
- Parity (1)
- Parity-P (1)
- Partial derivatives (2)
- Partition function (2)
- Paths (1)
- PCP (14)
- PCPs (1)
- Pebbling (1)
- Perfect hashing (1)
- Permanent (5)
- Permutation (3)
- Permutation group (1)
- Perturbation stability (1)
- Pfaffian (1)
- PH (1)
- Planted (2)
- Planted bisection (1)
- Planted CSP (1)
- Planted SAT (1)
- Polynomial - Littlewood (1)
- Polynomial approximation (5)
- Polynomial calculus (1)
- Polynomial factorization (1)
- Polynomial Identity Lemma (3)
- Polynomial Identity Testing (9)
- Polynomial mapping (1)
- Polynomial method (6)
- Polynomial threshold (3)
- Polynomial-time approximation scheme (1)
- Polynomial-time hierarchy (5)
- Polynomials (6)
- Polynomials - multivariate (31)
- Polynomials - univariate (4)
- Polytopes (1)
- Population recovery (1)
- Potential function (2)
- Pricing mechanism (1)
- Principal component analysis (1)
- Private information retrieval (1)
- Private learning (1)
- Probabilistic analysis (1)
- Probabilistically checkable proofs (13)
- Profiles (1)
- Projection (1)
- Projection Games Conjecture (1)
- Projections (1)
- Proof complexity (7)
- Propagation (1)
- Property testing (16)
- Provers (1)
- Pseudorandom generator (2)
- Pseudorandom generators (7)
- Pseudorandomness (4)
- PSPACE (1)
- PTAS (1)
- Pushdown graph (1)
Q
- QIP (1)
- QMA (7)
- Quadratic programming (1)
- Quantifier elimination (1)
- Quantiles (1)
- Quantum computing (47)
- Quantum communication (1)
- Quantum complexity (1)
- Quantum cryptography (2)
- Quantum entropy (1)
- Quantum games (1)
- Quantum Hamiltonian (1)
- Quantum information (4)
- Quantum interactive proofs (3)
- Quantum lower bounds (1)
- Quantum query complexity (3)
- Quantum rounding (1)
- Quantum sampling (1)
- Quantum statistical zero knowledge (1)
- Quantum supremacy (1)
- Quantum teleportation (1)
- Quantum walk (3)
- Quasipolynomial (1)
- Query complexity (18)
R
- Rényi entropy (1)
- Rademacher variables (1)
- Rainbow (1)
- RANDOM (24)
- RANDOM 2018 special issue (3)
- Random graphs (2)
- Random order arrival (1)
- Random permutation (1)
- Random polynomials (1)
- Random restrictions (1)
- Random sampling (3)
- Random self-reducibility (1)
- Random walk (4)
- Randomized (5)
- Randomized query complexity (2)
- Randomized reduction (3)
- Randomized rounding (2)
- Randomness (1)
- Rank (3)
- Rank -- algebraic (1)
- Rateless codes (1)
- Read-once formulas (1)
- Read-once polynomials (1)
- Reductions (1)
- Reed-Muller codes (2)
- Regret (2)
- Regularity lemma (2)
- Relativization (2)
- Representation theory (2)
- Research surveys (4)
- Resolution (2)
- Resource allocation (1)
- Reversibility (1)
- Ring (2)
- RL vs. L (1)
- Robust soundness (1)
- Routing (3)
- Routing games (1)
S
- Samplable distributions (1)
- Sample complexity (2)
- Sampling (3)
- Sampling complexity (1)
- Sanitization (1)
- SAT (10)
- Satisfiability (2)
- Scheduling (4)
- SDP gap (2)
- Search (2)
- Secret sharing (2)
- Security (1)
- Self-assembly (1)
- Semidefinite programming (7)
- Semigroups (1)
- Sensitivity (6)
- Separability (1)
- Separation of complexity classes (6)
- Separation of complexity measures (2)
- Separators (1)
- Set cover (1)
- Set-cover (1)
- SETH (1)
- #P (2)
- Sherali--Adams (1)
- Shifted partial derivatives (1)
- Short (43)
- Shortest paths (1)
- Shortest vector problem (2)
- Sign patterns (1)
- Sign-rank (1)
- Simulation (1)
- Simultaneous optimization (1)
- Skew circuits (1)
- Skew field (1)
- Sliding Scale Conjecture (1)
- Small-bias distribution (2)
- Small-set expansion (1)
- Smoothed analysis (1)
- Space (1)
- Space complexity (2)
- Span programs (2)
- Sparsification (1)
- Special issue (48)
- Spectral approximation (2)
- Spectral gap (1)
- Speed-scaling (1)
- Spherical means (1)
- Statistical physics (2)
- Stochastic block model (1)
- Stochastic calculus (1)
- Streaming (2)
- Strong chromatic number (1)
- Strong convexity (1)
- Subgraph density (1)
- Submodular (2)
- Submodular function (2)
- Sum-of-squares hierarchy (1)
- Sum-of-squares refutation (1)
- Summary (1)
- Sunflowers (1)
- Support size estimation (1)
- Surjectivity (1)
- Survivable networks (1)
- Switching lemma (1)
- Switching networks (1)
- Symmetry (1)
T
- Talagrand's concentration inequality (1)
- Tape (1)
- Tensor (1)
- Tensor network (1)
- Tensor product (1)
- Tensor product codes (1)
- Tensor rank (3)
- Tensors (2)
- Threshold (5)
- Threshold circuits (1)
- Threshold-rank (1)
- Tiling (2)
- Time-space tradeoff (2)
- Tomography (1)
- Tradeoff (1)
- Transform (1)
- Traveling salesman (3)
- Treewidth (2)
- Turing machine (1)
- Tutte polynomial (1)
U
- UG-hardness (6)
- Unate and monotone functions (1)
- Uniformity testing (1)
- Unique Games (7)
- Unique Games Conjecture (2)
- Unique witness (1)
V
- Vector balancing (1)
- Vertex deletion (1)
- Vertex-connectivity (1)
- Vision (1)
- VNP (1)
- Voronoi decomposition (1)
- Voting (1)