Arrow Research search

Author name cluster

Johan Håstad

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

41 papers
2 author rows

Possible papers

41

FOCS Conference 2023 Conference Paper

On small-depth Frege proofs for PHP

  • Johan Håstad

We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the $n \times n$ grid where n is odd. We are interested in the case where each formula in the proof is a depth d formula in the basis given by $\wedge, \vee$, and $\neg$. We prove that in this situation the proof needs to be of size exponential in $n^{\Omega(1 / d)}$. If we restrict the size of each line in the proof to be of size M then the number of lines needed is exponential in $n /(\log M)^{O(d)}$. The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.

Details

FOCS Conference 2022 Conference Paper

On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited

  • Johan Håstad
  • Kilian Risse

We study Frege proofs using depth-d Boolean formulas for the Tseitin contradiction on $n\times n$ grids. We prove that if each line in the proof is of size M then the number of lines is exponential in $n/(\log M)^{O(d)}$. This strengthens a recent result of Pitassi et al. [12]. The key technical step is a multi-switching lemma extending the switching lemma of Hastad [8] for a space of restrictions related to the Tseitin contradiction. The strengthened lemma also allows us to improve the lower bound for standard proof size of bounded depth Frege refutations from exponential in $\tilde{\Omega}(n^{1/59d})$ to exponential in $\tilde{\Omega}(n^{1/(2d-1)})$.

Details

SODA Conference 2021 Conference Paper

Explicit two-deletion codes with redundancy matching the existential bound

  • Venkatesan Guruswami
  • Johan Håstad

We give an explicit construction of length- n binary codes capable of correcting the deletion of two bits that have size 2 n / n 4+ o (1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2 n / n 4 ). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Ω(2 n / n 3+ o (1) ) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

Details

SODA Conference 2021 Conference Paper

Optimal Inapproximability with Universal Factor Graphs

  • Per Austrin
  • Jonah Brown-Cohen
  • Johan Håstad

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). Hardness of the “(2 + ∊ )-Sat” problem and other Promise CSPs (Austrin et al. , SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.

Details

FOCS Conference 2018 Conference Paper

Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs

  • Johan Håstad

This is the Knuth Prize lecture. We discuss the approximability of Boolean Constraint Satisfaction Problems (CSPs). In this situation we are given a large number of constraints, each of the form of a fixed predicate P applied to a sequence of literals. The goal is to find an assignment that satisfies the maximum number of constrains.

Details

FOCS Conference 2017 Conference Paper

On Small-Depth Frege Proofs for Tseitin for Grids

  • Johan Håstad

We prove a lower bound on the size of a small depth Frege refutation of the Tseitin contradiction on the grid. We conclude that polynomial size such refutations must use formulas of almost logarithmic depth.

Details

FOCS Conference 2016 Conference Paper

An Average-Case Depth Hierarchy Theorem for Higher Depth

  • Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and Tan [1] to address circuits of almost logarithmic depth. Our proof uses the same basic approach as [1] but a number of small differences enables us to obtain a stronger result by a significantly shorter proof.

Details

FOCS Conference 2014 Conference Paper

(2 + epsilon)-Sat Is NP-Hard

  • Per Austrin
  • Johan Håstad
  • Venkatesan Guruswami

We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2] - 1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT ∈ P as easiness of SAT when 1-in-2 literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when 1-in-3 literals are true, our resultshows, for any fixed ε > 0, the hardness of finding a satisfyingassignment to instances of "(2 + ε)-SAT" where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.

Details

FOCS Conference 2012 Conference Paper

Making the Long Code Shorter

  • Boaz Barak
  • Parikshit Gopalan
  • Johan Håstad
  • Raghu Meka
  • Prasad Raghavendra
  • David Steurer

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε >; 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - ε, but G's adjacency matrix has more than exp(log δ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K polylog(K), improving over the previously known gadget with blowup of 2 Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

Details

STOC Conference 2002 Conference Paper

On the advantage over a random assignment

  • Johan Håstad
  • Srinivasan Venkatesh 0001

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. Since the random assignment algorithm is known to give essentially the best possible polynomial time approximation algorithm for many optimization problems, this is a useful measure.In this paper, we focus on this measure for the optimization problems, Max-Lin-2, in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max- $k$ -Lin-2, a special case of the above problem in which each equation has at most $k$ variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization.

Details

FOCS Conference 2001 Conference Paper

Query Efficient PCPs with Perfect Completeness

  • Johan Håstad
  • Subhash Khot

For every integer k>1, we present a PCP characterization of NP where the verifier uses logarithmic randomness, queries 4k+k/sup 2/ bits in the proof, accepts a correct proof with probability 1 (i. e. it is has perfect completeness) and accepts any supposed proof of a false statement with a certain maximum probability. In particular, the verifier achieves optimal amortized query complexity of 1+/spl delta/ for arbitrarily small constant /spl delta/>0. Such a characterization was already proved by A. Samorodnitsky and L. Trevisan (2000), but their verifier loses perfect completeness and their proof makes an essential use of this feature. By using an adaptive verifier, we can decrease the number of query bits to 2k+k/sup 2/, the same number obtained by Samorodnitsky and Trevisan. Finally, we extend some of the results to larger domains.

Details

FOCS Conference 2000 Conference Paper

Hardness of Approximate Hypergraph Coloring

  • Venkatesan Guruswami
  • Johan Håstad
  • Madhu Sudan 0001

We introduce the notion of covering complexity of a probabilistic verifier. The covering complexity of a verifier on a given input is the minimum number of proofs needed to "satisfy" the verifier on every random string, i. e. , on every random string, at least one of the given proofs must be accepted by the verifier. The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems, and in particular (hyper)-graph coloring problems. We present a PCP verifier for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a super-constant covering complexity for statements not in the language. Moreover the acceptance predicate of this verifier is a simple Not-all-Equal check on the four bits it reads. This enables us to prove that for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors, and also yields a super-constant inapproximability result under a stronger hardness assumption.

Details

FOCS Conference 1998 Conference Paper

The Security of Individual RSA Bits

  • Johan Håstad
  • Mats Näslund

We study the security of individual bits in an RSA encrypted message E/sub N/(X). We show that given E/sub N/(X), predicting any single bit in x with only a non-negligible advantage over the trivial guessing strategy is (through a polynomial time reduction) as hard as breaking RSA. We briefly discuss a related result for bit security of the discrete logarithm.

Details

FOCS Conference 1996 Conference Paper

Clique is Hard to Approximate Within n 1-epsilon

  • Johan Håstad

The author proves that unless NP=coR, Max Clique is hard to approximate in polynomial time within a factor n/sup 1-/spl epsiv// for any /spl epsiv/>0. This is done by, for any /spl delta/>0, constructing a proof system for NP which uses /spl delta/ amortized free bits. A central lemma, which might be of independent interest, gives sufficient conditions (in the form of a certain type of agreement) for creating a global function from local functions certain local consistency conditions.

Details

FOCS Conference 1995 Conference Paper

Linearity Testing in Characteristic Two

  • Mihir Bellare
  • Don Coppersmith
  • Johan Håstad
  • Marcos A. Kiwi
  • Madhu Sudan 0001

Let Dist(f, g)=Pr/sub u/ [f(u)/spl ne/g(u)] denote the relative distance between functions f, g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f, g). Given a function f: G/spl rarr/H we let Err(f)=Pr/sub u/, v[f(u)+f(v)/spl ne/f(u+v)] denote the rejection probability of the BLR (Blum-Luby-Rubinfeld) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular the study of lower bounds on Err(f) in terms of Dist(f). The case we are interested in is when the underlying groups are G=GF(2)/sup n/ and H=GF(2). The corresponding test is used in the construction of efficient PCPs and thence in the derivation of hardness of approximation results, and, in this context, improved analyses translate into better non-approximability results. However, while several analyses of the relation of Err(f) to Dist(f) are known, none is tight. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete (i. e. tight) in some. In particular we present functions L, U: [0, 1]/spl rarr/[0, 1] such that for all x/spl isin/[0, 1] we have L(x)<Err(f)/spl les/U(x) whenever Dist(f)=x, with the upper bound being tight on the whole range, and the lower bound tight on a large part of the range and close on the rest. Part of our strengthening is obtained by showing a new connection between the linearity testing problem and Fourier analysis, a connection which may be of independent interest. Our results are used by M. Bellare et al. (1995) to present the best known hardness results for Max3SAT and other MaxSNP problems.

Details

FOCS Conference 1993 Conference Paper

The shrinkage exponent is 2

  • Johan Håstad

We prove that if we hit a formula of size L with a random restriction from R/sub p/ then the expected remaining size is at most O(p/sup 2/(log p)/sup 3/2/L). As a corollary we obtain a R(n/sup 3-O(1)/) formula size lower bound for an explicit function in NP. >

Details

FOCS Conference 1993 Conference Paper

Top-Down Lower Bounds for Depth 3 Circuits

  • Johan Håstad
  • Stasys Jukna
  • Pavel Pudlák

We present a top-down lower bound method for depth 3 AND-OR-NOT circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular we prove that depth 3 AND-OR-NOT circuits that compute PARITY resp. MAJORITY require size at least 2/sup 0. 618/. .. /spl radic/n/ resp. 2/sup 0. 849/. .. /spl radic/n/. This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits. >

Details

FOCS Conference 1990 Conference Paper

On the Power of Small-Depth Threshold Circuits

  • Johan Håstad
  • Mikael Goldmann

The power of threshold circuits of small depth is investigated. In particular, functions that require exponential-size unweighted threshold circuits of depth 3 when the bottom fan-in is restricted are given. It is proved that there are monotone functions f/sub k/ that can be computed on depth k and linear size AND, OR circuits but require exponential-size to be computed by a depth-(k-1) monotone weighted threshold circuit. >

Details

FOCS Conference 1990 Conference Paper

Simple Constructions of Almost k-Wise Independent Random Variables

  • Noga Alon
  • Oded Goldreich 0001
  • Johan Håstad
  • René Peralta 0001

The authors present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is O(log log n+k+log 1/ epsilon ), where epsilon is the statistical difference between the distribution induced on any k-bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by J. Naor and M. Naor (1990). An advantage of the present constructions is their simplicity. Two of the constructions are based on bit sequences that are widely believed to possess randomness properties, and the results can be viewed as an explanation and establishment of these beliefs. >

Details

FOCS Conference 1987 Conference Paper

Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds

  • William Aiello
  • Johan Håstad

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w ∈ L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.

Details

FOCS Conference 1986 Conference Paper

On the Power of Interaction

  • William Aiello
  • Shafi Goldwasser
  • Johan Håstad

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [B], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string x is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept x. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject x with small probability. The class IP[f(|x|)] is said to contain L if, there exists an interactive proof system with f(|x|)- message exchanges (interactions) such that with high probability the verifier accepts x if and only if x ε L. Babai [B] showed that all languages recognized by interactive proof systems with bounded number of interactions, can be recognized by interactive proof systems with only two interactions. Namely, for every constant k, IP[k] collapses to Ip[2]. In this paper, we give evidence that interactive proof systems with unbounded number of interactions may be more powerful than interactive proof systems with bounded number of interactions. We show that for any unbounded function f(n) there exists an oracle B such that IPB [f(|x|)] ⊄ PHB. This implies that IPB[f(n)] ≠ IPB[2], since IPB[2] ⊆ Π2B for all oracles B. The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].

Details

FOCS Conference 1985 Conference Paper

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

  • Benny Chor
  • Oded Goldreich 0001
  • Johan Håstad
  • Joel Friedman
  • Steven Rudich
  • Roman Smolensky

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f: {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f: {0, 1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.

Details