The following pages link to Johan T. Håstad (Q1083474):
Displaying 50 items.
- (Q293358) (redirect page) (← links)
- On the complexity of interactive proofs with bounded communication (Q293359) (← links)
- One-way multiparty communication lower bound for pointer jumping with applications (Q532058) (← links)
- (Q593210) (redirect page) (← links)
- On the approximation resistance of a random predicate (Q626662) (← links)
- On the power of small-depth threshold circuits (Q685717) (← links)
- A well-characterized approximation problem (Q688442) (← links)
- On the power of interaction (Q751809) (← links)
- Statistical zero-knowledge languages can be recognized in two rounds (Q808692) (← links)
- Relativized perfect zero knowledge is not BPP (Q811120) (← links)
- The security of the IAPM and IACBC modes (Q877808) (← links)
- Simultaneous diophantine approximation of rationals by rationals (Q1083475) (← links)
- Dual vectors and lower bounds for the nearest lattice point problem (Q1107568) (← links)
- Does co-NP have short interactive proofs ? (Q1108004) (← links)
- One-way permutations in NC 0 (Q1108786) (← links)
- Simultaneously good bases of a lattice and its reciprocal lattice (Q1119682) (← links)
- On approximating NP-hard optimization problems (Q1126838) (← links)
- A simple lower bound for monotone clique using a communication game (Q1190521) (← links)
- Majority gates vs. general weighted threshold gates (Q1210330) (← links)
- On average time hierarchies (Q1313704) (← links)
- The discrete logarithm modulo a composite hides \(O(n)\) bits (Q1317484) (← links)
- On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\) (Q1320512) (← links)
- Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\) (Q1322486) (← links)
- Virtual shared memory: Algorithms and complexity (Q1333257) (← links)
- The random oracle hypothesis is false (Q1333397) (← links)
- On the shrinkage exponent for read-once formulae (Q1367534) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- A slight sharpening of LMN (Q1604204) (← links)
- On bounded occurrence constraint satisfaction (Q1607037) (← links)
- Quantum algorithms for computing short discrete logarithms and factoring RSA integers (Q1673620) (← links)
- Top-down lower bounds for depth-three circuits (Q1904663) (← links)
- \(d\)-Galvin families (Q2294104) (← links)
- Practical construction and analysis of pseudo-randomness primitives (Q2482337) (← links)
- On Lower Bounds for Selecting the Median (Q2719173) (← links)
- A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p (Q2729649) (← links)
- On the list-decodability of random linear codes (Q2875168) (← links)
- On the usefulness of predicates (Q2947573) (← links)
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (Q2968149) (← links)
- An Improved Bound on the Fraction of Correctable Deletions (Q2979079) (← links)
- On the power of many one-bit provers (Q2986871) (← links)
- Randomly Supported Independence and Resistance (Q2999851) (← links)
- (Q3002760) (← links)
- (Q3002788) (← links)
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers (Q3033848) (← links)
- Satisfying Degree-d Equations over GF[2] n (Q3088098) (← links)
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant (Q3093627) (← links)
- Linearity testing in characteristic two (Q3129465) (← links)
- Hardness of Approximate Hypergraph Coloring (Q3149889) (← links)
- On the NP-Hardness of Max-Not-2 (Q3167394) (← links)
- (Q3191584) (← links)
