yusuke1997/dblp-id-title huggingface dataset:
Alternating Time Versus Deterministic Time: A Separation
Inductive Reasoning and Komogorov Complexity
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems
Fault Tolerant Circuits and Probabilistically Checkable Proofs
Directed Planar Reachability is in Unambiguous Log-Space
Gap-Definable Counting Classes
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
Multi-Prover Encoding Schemes and Three-Prover Proof Systems
Inapproximability Some history and some open problems
A Duality between Clause Width and Clause Density for SAT
Relative to a Random Oracle, NP is Not Small
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
The Correlation Between Parity and Quadratic Polynomials Mod 3
The Space Complexity of Cutting Planes Refutations
34th Computational Complexity Conference, CCC 2019, New Brunswick, NJ, USA, July 18-20, 2019
Derandomized Parallel Repetition of Structured PCPs
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity
Towards the Parallel Repetition Conjecture
IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014
Pointers versus Arithmetic in PRAMs
Complexity Classification of Two-Qubit Commuting Hamiltonians
On Polynomial Time Turing and Many-One Completeness in PSPACE
Short PCPs Verifiable in Polylogarithmic Time
Optimal Short-Circuit Resilient Formulas
Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State
Hardness Amplification within NP against Deterministic Algorithms
Sculpting Quantum Speedups
Decision Trees with AND, OR Queries
New Hardness Results for Graph and Hypergraph Colorings
Radical Sylvester-Gallai Theorem for Tuples of Quadratics
Links Between Complexity Theory and Constrained Block Coding
Computational Indistinguishability: A Sample Hierarchy
An Oarcle Builder's Toolkit
On polynomial and generalized complexity cores
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε
Further Collapses in TFNP
How to Encode a Logical Structure by an OBDD
Low-Depth Algebraic Circuit Lower Bounds over Any Field
Relativized limitations of left set technique and closure classes of sparse sets (Extended Abstract)
Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance
Hausdorff Dimension in Exponential Time
Sherali - Adams Strikes Back
Recent Progress on Lower Bounds for Arithmetic Circuits
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Bounded-Depth Circuits Cannot Sample Good Codes
Hardness vs. Randomness - A Survey (abstract)
Some Lower and Upper Bounds for Algebraic Decision Trees and the Separation Problem
S-T Connectivity on Digraphs with a Known Stationary Distribution
Separation of NP-Completeness Notions
Applications of the Sum-Product Theorem in Finite Fields
Approximation and Small Depth Frege Proofs
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability
The Complexity of Sparse Sets in P
Fixed-Polynomial Size Circuit Bounds
Applications of a New Transference Theorem to Ajtai's Connection Factor
Uniform Circuits for Division: Consequences and Problems
Testing Properties of Constraint-Graphs
Rectangle Size Bounds and Threshold Covers in Communication Complexity
Fractional Covers and Communication Complexity
22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA
Polynomial Identity Testing for Depth 3 Circuits
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001
Universal Languages and the Power of Diagonalization
On the Structure of Bounded Queries to Arbitrary NP Sets
Polynomial-Time Membership Comparable Sets
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion
Tight Bounds for Stream Decodable Error-Correcting Codes
On Bounded Round Multi-Prover Interactive Proof Systems
Mining Circuit Lower Bound Proofs for Meta-algorithms
On Approximation Algorithms for Hierarchical MAX-SAT
Optimal Separation and Strong Direct Sum for Randomized Query Complexity
The Complexity of the Inertia and Some Closure Properties of GapL
Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem
Lower Bounds and Separations for Constant Depth Multilinear Circuits
The Computational Complexity of Elliptic Partial Differential Equations
A Comparison of Weak Completeness Notions
Resource- Bounded Kolmogorov Complexity of Hard Languages
Generic Separations
Time-Space Tradeoffs in the Counting Hierarchy
On the Power of Quantum Proofs
On the Parameterized and Approximation Hardness of Metric Dimension
Learning Algorithms from Natural Proofs
The Quantitative Structure of Exponential Time
On Sets with Efficient Implicit Membership Tests
From DNF Compression to Sunflower Theorems via Regularity
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK
The Power of Negative Thinking in Constructing Threshold Circuits for Addition
Complexity Classes and Sparse Oracles
Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems
On the Pseudo-Deterministic Query Complexity of NP Search Problems
On the Satisfaction Probability of k-CNF Formulas
Enumerative counting is hard
A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph
On Finding Locally Optimal Solutions
Making Hard Problems Harder
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications
On the Power of Nonlinear Secrect-Sharing
The Complexity of Iterated Multiplication
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998
Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas
Juris Hartmanis: fundamental contributions to isomorphism problems
Parallel Iteration Methods
SOS Lower Bound for Exact Planted Clique
Impossibilities and Possibilities of Weak Separation Between NP and Exponential Time
With Quasi-linear Queries, EXP is not Polynomial Time Turing Reducible to ?Sparse Sets
A Majority Lemma for Randomised Query Complexity
A Note on Amortized Branching Program Complexity
Low-Depth Witnesses are Easy to Find
On the Isomorphism Problem for Weak Reducibilities
List Decoding Quotient Reed-Muller Codes
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity
On the Power and Limitations of Branch and Cut
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation
A New Approach to Affine Extractors and Dispersers
A Nonadaptive NC Checker for Permutation Group Intersection
A Survey on Counting Classes
Descriptive Complexity of #P Functions
Locally Testable Codes Require Redundant Testers
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols
A Game-Theoretic Classification of Interactive Complexity Classes
Interactive Proof Systems with Polynomially Bounded Strategies
Randomization and Derandomization in Space_Bounded Computation
Logical Operations and Kolmogorov Complexity II
Separation of the Factorization Norm and Randomized Communication Complexity
Inverting the Turing Jump in Complexity Theory
On Randomized Reductions to the Random Strings
Dimension Independent Disentanglers from Unentanglement and Applications
On Randomness Extraction in AC0
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem
Finding Errorless Pessiland in Error-Prone Heuristica
Characterization of complexity classes in higher-order logic
Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In
Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y"
Expressibility as a complexity measure: results and directions
Derandomizing Logspace with a Small Shared Hard Drive
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
Biased Linearity Testing in the 1% Regime
Integer Programming as a Framework for Optimization and Approximability
On the Random-Self-Reducibility of Complete Sets
Statistical Physics Approaches to Unique Games
On P-Immunity of Nondeterministic Complete Sets
Extensions to Barrington's M-Program Model
The strong exponential hierarchy collapses
Amplifying Lower Bounds by Means of Self-Reducibility
Settling the Query Complexity of Non-Adaptive Junta Testing
VC Dimension in Circuit Complexity
The Proof Complexity of Polynomial Identities
Independent Minimum Length Programs to Translate between Given Strings
Algebras of Minimal Rank over Perfect Fields
Bounded Queries in Recursion Theory: A Survey
The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial (abstract)
Augmented Index and Quantum Streaming Algorithms for DYCK(2)
Computing from Partial Solutions
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
On the Sensitivity of Cyclically-Invariant Boolean Functions
Non-Automatizability of Bounded-Depth Frege Proofs
Deciding the K-Dimension is PSPACE-Complete
The Complexity of Selecting Maximal Solutions
Hardness vs Randomness for Bounded Depth Arithmetic Circuits
On the Complexity of Approximating the VC Dimension
FO[<]-Uniformity
On the Hardness of Approximating Multicut and Sparsest-Cut
Switching Graph Matrix Norm Bounds: From i.i.d. to Random Regular Graphs
Combinatorial Interpretation of Kolmogorov Complexity
Errata for Circuit Size to Pseudorandom Oracles
Pseudorandomness for Approximate Counting and Sampling
On the Structure of Complete Sets
Monotone Simulations of Nonmonotone Proofs
Polynomial time reducibility to a set of small density
Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds
On the Query Complexity of Clique Size and Maximum Satisfiability
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT
Lower Bounds for Matrix Factorization
On Functions Computable with Nonadaptive Queries to NP
Fractional Pseudorandom Generators from Any Fourier Level
Quasipolynomial Size Circuit Classes
Some consequences of the existence of pseudorandom generators
Explicit Time and Space Efficient Encoders Exist Only with Random Access
Constructing Hard Functions Using Learning Algorithms
Covering CSPs
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009
Reversible Simulation of Irreversible Computation
2-Transitivity Is Insufficient for Local Testability
Spectral Expanding Expanders
Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA
Factorization of Polynomials Given By Arithmetic Branching Programs
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing
On Communication over an Entanglement-Assisted Quantum Channel
A Strong Direct Product Theorem for Quantum Query Complexity
Noisy Interpolating Sets for Low Degree Polynomials
Arithmetic Circuits with Locally Low Algebraic Rank
Infinite vs. Finite Space-Bounded Randomized Computations
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy
Equality Alone Does not Simulate Randomness
The Topology of Provability in Complexity Theory
On the Complexity of Succinct Zero-Sum Games
A Linear Time Algorithm for Quantum 2-SAT
AM with Multiple Merlins
Linear Sketching over F_2
Extractors for Low-Weight Affine Sources
Palette-Alternating Tree Codes
On ranking
The Instance Complexity Conjecture
The Partition Bound for Classical Communication Complexity and Query Complexity
Fourier Bounds and Pseudorandom Generators for Product Tests
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract)
Solvable Group Isomorphism
Communication Complexity under Product and Nonproduct Distributions
Capturing Complexity Classes by Fragments of Second Order Logic
Amortized Closure and Its Applications in Lifting for Resolution over Parities
Probabilistic Game Automata
A New Characterization of ACC 0 and Probabilistic CC 0
On the Automatability of Tree-Like k-DNF Resolution
Exponential Time and Subexponential Time Sets
New Results on the Complexity of the Middle Bit of Multiplication
Computational Complexity and Phase Transitions
Constant-Depth Circuits vs. Monotone Circuits
Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size
A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP
Pseudorandomness and Average-Case Complexity via Uniform Reductions
Are PCPs Inherent in Efficient Arguments?
A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs
Noise Stability Is Computable and Approximately Low-Dimensional
Hardness Amplification for Non-Commutative Arithmetic Circuits
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements
Algebraic Metacomplexity and Representation Theory
A Note on the Hardness of Tree Isomorphism
21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic
NP with Small Advice
Towards Free Lunch Derandomization from Necessary Assumptions (And OWFs)
Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions
Tolerant Versus Intolerant Testing for Boolean Properties
Generalised Linial-Nisan Conjecture Is False for DNFs
Graph Ramsey Theory and the Polynomial Hierarchy (Abstract)
Topology Inside NC¹
Towards Dimension Expanders over Finite Fields
Near-Optimal Averaging Samplers and Matrix Samplers
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
Time Bounded Frequency Computations
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
Hardness of Max 3SAT with No Mixed Clauses
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem
A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials
The Communication Complexity of Correlation
The Quantifier Structure of Sentences that Characterize Nondeterministic Time Complexity
Truth-table Closure and Turing Closure of Average Polynomial Time have Different Measures in EXP
On the Power of Randomness in the Decision Tree Model
Sperner's Lemma and Robust Machines
Property Testing Lower Bounds via Communication Complexity
The Plane Test Is a Local Tester for Multiplicity Codes
The Entangled Quantum Polynomial Hierarchy Collapses
Improved Constructions of Three Source Extractors
Average-Case Computations - Comparing AvgP, HP, and Nearly-P
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
Unprovably intractable languages
Perceptrons, PP, and the Polynomial Hierarchy
Diagonalisation methods in a polynomial setting
Derandomizing Isolation in Space-Bounded Settings
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA
Evolution and Computation (Invited Talk)
A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting
A Strong Parallel Repetition Theorem for Projection Games on Expanders
Improved Direct Product Theorems for Randomized Query Complexity
PP is Closed Under Truth-Table Reductions
Linear List-Approximation for Short Programs (or the Power of a Few Random Bits)
A Direct Product Theorem for One-Way Quantum Communication
On Closeness of NP-Hard Sets to Other Complexity Classes
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness
The Computational Complexity of Integer Programming with Alternations
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997
Linear Branching Programs and Directional Affine Extractors
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
Randomness is Hard
On the Closest Vector Problem with a Distance Guarantee
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
Approximation Resistant Predicates from Pairwise Independence
Predicate Classes and Promise Classes
A Simple Proof of a New Set Disjointness with Applications to Data Streams
A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates
Optimal Quantum Sample Complexity of Learning Algorithms
On Closure Properties of #P in the Context of PF°#P
The Power of the Queue
LR(k) Testing is Average Case Complete
32nd Computational Complexity Conference, CCC 2017, Riga, Latvia, July 6-9, 2017
Exposure-Resilient Extractors
Hitting Sets for Low-Degree Polynomials with Optimal Density
Baby PIH: Parameterized Inapproximability of Min CSP
On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity
Towards Lower Bounds on Locally Testable Codes via Density Arguments
On the Hardness of 4-Coloring a 3-Colorable Graph
An Approximation Algorithm for Approximation Rank
Pseudorandomness for Permutation and Regular Branching Programs
Vertex Cover Might be Hard to Approximate to within 2-\varepsilon
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
One-way functions, robustness, and the non-isomorphism of NP-complete sets
Polynomial Time Algorithms in Invariant Theory for Torus Actions
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
DNA Models and Algorithms for NP-complete Problems
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits
Complicated Complementations
Optimal Hardness Results for Maximizing Agreements with Monomials
The Quantum Adversary Method and Classical Formula Size Lower Bounds
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting
Better Condensers and New Extractors from Parvaresh-Vardy Codes
Pseudorandom Generators from Polarizing Random Walks
Some Recent Progress on the Complexity of Lattice Problems
Six Hypotheses in Search of a Theorem
Counting the Number of Perfect Matchings in K5-Free Graphs
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
Parity Helps to Compute Majority
The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract)
Bounded Arithmetic and Computational Complexity
Directed st-Connectivity with Few Paths Is in Quantum Logspace
On the Computational Complexity of Small Descriptions
Border Complexity of Symbolic Determinant Under Rank One Restriction
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard
Set Bit Enumeration is Hard
Computing in Fault Tolerance Broadcast Networks
An Excursion to the Kolmogorov Random Strings
An Almost Optimal Rank Bound for Depth-3 Identities
The Power of Witness Reduction
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem
Time, Hardware, and Uniformity
Improved Pseudorandom Generators for AC⁰ Circuits
DSPACE[n k ] = VAR[k+1]
Using Entanglement in Quantum Multi-prover Interactive Proofs
Worst-Case to Average Case Reductions for the Distance to a Code
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Average-Case Quantum Advantage with Shallow Circuits
Using Bounded Query Classes to Separate Classes in the Exponential Time Hierarchy from Classes in PH
Shared Randomness and Quantum Communication in the Multi-party Model
Locally Dense Codes
On Medium-Uniformity and Circuit Lower Bounds
Relations between communication complexity classes
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model
Lower Bounds for Computation with Limited Nondeterminism
The Law of the Iterated Logarithm for p-Random Sequences
Just a Pebble Game
On helping by robust oracle machines
Relativized Alternation
Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988
Communication Complexity with Synchronized Clocks
Constructions of Low-Degree and Error-Correcting in-Biased Generators
LS+ Lower Bounds from Pairwise Independence
A Composition Theorem for Conical Juntas
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
Average Case Complexity of Unbounded Fanin Circuits
Lower Bounds for Testing Properties of Functions over Hypergrid Domains
The General Notion of a Dot-Operator
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth
Learning Monotone Decision Trees in Polynomial Time
Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure
Solving Linear Equations by Means of Scalar Products
Leakage-Resilient Hardness vs Randomness
Symmetric LDPC Codes are not Necessarily Locally Testable
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
Resource bounded baire category and small circuits in exponential space
Pseudorandom Bits for Non-Commutative Programs
A Min-Entropy Approach to Multi-Party Communication Lower Bounds
Unambiguity of Circuits
Juris Hartmanis: the beginnings of computational complexity
A New Approach for Constructing Low-Error, Two-Source Extractors
On the (Non) NP-Hardness of Computing Circuit Complexity
Downward separation fails catastrophically for limited nondeterminism classes
Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers
On the Ring Isomorphism and Automorphism Problems
Pseudorandom Generators without the XOR Lemma (Abstract)
Failure of Feasible Disjunction Property for k-DNF Resolution and NP-Hardness of Automating It
A Short Guide to Approximation Preserving Reductions
Proving SAT does not have Small Circuits with an Application to the Two
Lower Bounds with Smaller Domain Size On Concurrent Write Parallel Machines
Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces
The Correct Exponent for the Gotsman-Linial Conjecture
Derandomization from Time-Space Tradeoffs
k-Independent Gaussians Fool Polynomial Threshold Functions
E-mail and the Unexpected Power of Interaction
Godel and Computations (Abstract)
On Algebraic Branching Programs of Small Width
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols
On the Power of Non-adaptive Learning Graphs
Complexity Classes Defined via k-valued Functions
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract)
On Basing ZK ≠ BPP on the Hardness of PAC Learning
Reductions between Expansion Problems
The Complexity of the Annihilating Polynomial
Pseudo-Random Generators for All Hardnesses
Dimension, Entropy Rates, and Compression
Every Linear Threshold Function has a Low-Weight Approximator
Derandomizing from Random Strings
On Finding the Number of Graph Automorphisms
On the Complexity of the Monotonicity Verification
Relationships Among PL, #L, and the Determinant
Algebraic Hardness Versus Randomness in Low Characteristic
Trading Time and Space in Catalytic Branching Programs
A Composition Theorem for Parity Kill Number
Exact Threshold Circuits
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching
Is Valiant-Vazirani's Isolation Probability Improvable?
Three-Query PCPs with Perfect Completeness over non-Boolean Domains
A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions
An n log n Algorithm to Distribute n Records Optimally in a Sequential Access File
Tight Bound on Johnson's Algoritihm for Max-SAT
On Approximate Majority and Probabilistic Time
Algebras of Minimal Multiplicative Complexity
Polynomial terse sets
The Quantum Challenge to Structural Complexity Theory
Resource-Bounded Baire Category: A Stronger Approach
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
Amplifying ZPP^SAT[1] and the Two Queries Problem