On Extremal Properties of k-CNF: Capturing Threshold Functions

Marvin K\"unnemann; Mohit Gurumukhani; Ramamohan Paturi

REVIEW 3 major objections 4 minor 15 references

On Extremal Properties of k-CNF: Capturing Threshold Functions

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper pins down exactly how many weight-$t$ assignments a $t$-admissible 2-CNF can accept, and shows that for thresholds near $n$ the problem becomes the Turán problem.

desk verdict Lemma 13's t-admissibility step is genuinely broken, but the paper's Turán equivalence and adaptive construction are solid enough to warrant a serious referee. read the letter →

arxiv 2412.20493 v1 pith:GVXTC2HR submitted 2024-12-29 cs.CC

Mohit Gurumukhani , Marvin Künnemann , Ramamohan Paturi This is my paper · ORCID

classification cs.CC MSC 05C3505C6905D05

keywords k-CNFthresholdfunctionscircuitlowerboundsTuránproblemmaximalindependentsetsSteinersystemsdepth-3circuitsextremalcombinatorics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks: among $k$-CNF formulas that reject every assignment with fewer than $t$ ones, what is the largest number of assignments with exactly $t$ ones they can accept? It answers this exactly for $k=2$, giving $S(n,t,2)=q^{n-t-r}(q+1)^r$ when $n=(n-t)q+r$, by reducing the problem to counting maximal independent sets of fixed size in a graph. For general $k$ it shows the threshold $t=n-k$ coincides with the classical Turán hypergraph problem, so a closed form for all $t$ would solve a famous open extremal problem. It also constructs adaptive block formulas for linear thresholds and conjectures they are optimal, which would push depth-3 circuit lower bounds for threshold functions from $2^{\Omega(n/k)}$ to $2^{\Omega((n/k)\log k)}$.

What carries the argument

The proof rests on several distinct mechanisms. The adaptive block construction splits variables into blocks of size $b=(k-1)/(1-\alpha)$, where each block realizes a perfect threshold at its own scale, producing the lower bound $\binom{b}{\alpha b}^{n/b}$. For $k=2$, a cycle-breaking step on the implication graph of an optimal formula, followed by an elimination of negative literals, yields an acyclic monotone 2-CNF with the same count of weight-$t$ satisfying assignments; those assignments correspond one-to-one with maximal independent sets of size $n-t$ in the clause graph. A recent bound on the maximum number of maximal independent sets of a fixed size in an $n$-vertex graph supplies the final upper bound. For $t=n-k$, a set-system duality shows that a monotone $k$-CNF with only width-$k$ clauses is equivalent to a $k$-uniform covering family, giving $S(n,n-k,k)=\binom{n}{k}-T(n,k+1,k)$, where $T$ is the Turán number.

What would settle it

Enumerate all 2-CNFs on $n\le 8$ variables and compute $S(n,t,2)$ by brute force; a single value differing from $q^{n-t-r}(q+1)^r$ would disprove Theorem 12. Separately, search for an optimal $t$-admissible 2-CNF where applying the lemma's literal substitution produces a formula accepting a weight-$(t-1)$ assignment not accepted by the original, which would invalidate the proof's reduction step.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the extremal threshold-capture problem $S(n,t,k)$ has a clean solution in the width-2 case and a deep combinatorial obstruction in general. For $k=2$, every optimal $t$-admissible formula can be taken acyclic and monotone, and the accepted weight-$t$ assignments correspond bijectively to maximal independent sets of size $n-t$ in the formula's clause graph; together with a bound on the number of such independent sets, this yields $S(n,t,2)=q^{n-t-r}(q+1)^r$. For general $k$, the paper proves that $S(n,n-k,k)=\binom{n}{k}-T(n,k+1,k)$, equating the problem at threshold $n-k$ with the Turán problem for $(k+1)$-uniform set families, and shows that when $n-k$ and $t$ are constant the extremal value is governed by the existence of Steiner systems. For intermediate linear thresholds $t=\alpha n$, it constructs block formulas that beat the naive uniform partition and conjectures their optimality.

Load-bearing premise

The $k=2$ upper bound depends on an unverified case in the cycle-removal lemma: it does not rule out that the transformed formula accepts a weight-$(t-1)$ assignment whose $x$-flip satisfies the original formula, and the paper offers no proof that this cannot happen in an optimal formula.

Editorial extensions

If this is right

For $k=2$, the quantity $S(n,t,2)$ is now known exactly for every $n$ and $t$, so the expressiveness of 2-CNF formulas for thresholds is closed.
For $t=n-k$, any progress on the Turán number $T(n,k+1,k)$ immediately translates into the extremal threshold-capture value, and vice versa.
For linear thresholds $t=\alpha n$, the adaptive block construction beats the naive uniform partition, and proving its optimality would show that $\mathrm{THR}_{\alpha n}$ requires $\Sigma\Pi\Sigma_k$ circuits of size $2^{\Omega(n/k \log k)}$.
When $n-k$ and $t$ are constant, extremal formulas exist exactly when the corresponding Steiner systems exist, with explicit value $\binom{n}{t-1}\cdot k/t$.
If the main conjecture holds, the known depth-3 circuit lower bounds for threshold functions improve asymptotically, closing a gap to matching upper-bound constructions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension the authors leave implicit: the $k=2$ closed form implies a 'rounding' formula for all $k$ if one conjectures that optimal formulas are products of independent blocks, with each block at the largest threshold it can express; the Turán equivalence shows this cannot hold universally without resolving the covering problem.
The unverified case in the cycle-removal lemma could be checked by a small exhaustive search; if a counterexample turns up, the exact $k=2$ formula would need a modified proof strategy even if the formula itself survives.
The Turán equivalence gives a two-way street: any improved upper or lower bound on $T(n,k+1,k)$ yields a corresponding bound on $S(n,n-k,k)$, so circuit-complexity tools might be brought to bear on extremal hypergraph problems.
The observation that optimality is only needed at $t=n^{o(k)}$ to improve circuit bounds suggests a weaker conjecture that might be easier to prove than full optimality at $t=\alpha n$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The stress-test note is right: Lemma 13 has a real gap, and the k=2 upper bound is not proven as written. The counterexample works. Take n=5, t=3 and F = (x1∨x2)∧(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(¬x1∨¬x2). It is 3-admissible with |sat_3(F)|=6, and the substitution in Lemma 13 yields F' that accepts the weight-2 assignment (0,0,1,1,0). So the reduction to acyclic formulas fails for the proof given. That is the flagship result, so the paper needs revision before Theorem 12 is taken as established.

But I would not throw the paper out. The Turán equivalence (Theorem 1) is a clean and genuinely new observation, and it explains why the general case is hard. The small-threshold uniqueness proof is nice, the Steiner-system connection is interesting, and the adaptive construction plus its circuit lower-bound consequence is a solid contribution even if Conjecture 2 needs qualification. The authors are also honest: they flag Wolfovitz's oversight and note that Amano disproved Conjecture 2 for k=4.

The soft spots are the gap in Lemma 13 and the sloppy statement of Conjecture 2. As printed, it covers all k≥2, while the paper's own related-work paragraph says it is false for k=4. That should be fixed with an odd-k conjecture or a caveat. Neither issue is fatal to the paper's value, but the burden falls on the proof of Theorem 12.

I would accept this for peer review. The ideas are worth refereeing, and the gap may be repairable. For a reading group, I would bring it to talk about the Turán connection and the adversarial flavor of the t-admissibility transformation. Recommendation: send to a serious referee, but flag Lemma 13 prominently. The authors should be asked to fix the proof or state Theorem 12 as conditional.

Referee Report

3 major / 4 minor

Summary. This paper studies S(n,t,k), the maximum number of Hamming-weight-t assignments accepted by a t-admissible k-CNF formula. The main results are: (i) an exact small-threshold result S(n,t,k)=k^t with a uniqueness statement; (ii) an adaptive block construction for linear thresholds t=alpha n with conjectured optimality; (iii) the exact formula S(n,t,2)=q^{n-t-r}(q+1)^r for all t, where n=(n-t)q+r; (iv) an equivalence for t=n-k between S(n,n-k,k) and the Turan number T(n,k+1,k); and (v) a connection to Steiner systems yielding exact values when appropriate designs exist. The paper also derives conditional depth-3 circuit lower bounds from the optimality conjecture for the adaptive construction.

Significance. If the k=2 result and the Turan equivalence are correct, the paper resolves a natural extremal question for all 2-CNF formulas and gives a clean new bridge between threshold-capture and classical Turan-type problems. The proofs rely on independent external results (Song-Yao on maximal independent sets, Keevash on designs, standard entropy bounds), and the paper contains no fitted parameters. The significance is conditional, however: the upper-bound proof for the central k=2 theorem currently rests on a transformation whose t-admissibility preservation is not established, and the manuscript's own later note states that Conjecture 2 is false for k=4.

major comments (3)

[§4, Lemma 13] Lemma 13's transformation does not preserve t-admissibility as claimed. In the proof, from F'(alpha)=1 and F_{x<-Y}(alpha)=1, the authors infer F(alpha)=1; this only follows when alpha(x)=alpha(Y), and the case alpha(x)=0, alpha(Y)=1 is never excluded. The gap is concrete: for n=5, t=3, take F=(x1∨x2)∧(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(¬x1∨¬x2). This F is 3-admissible and has |sat3(F)|=6, matching Theorem 12 with q=2, r=1, and x1 and ¬x2 lie on a cycle in G(F). Applying the Lemma 13 construction with X=x1, Y=¬x2 yields F'=(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(x1∨¬x2), and the weight-2 assignment (0,0,1,1,0) satisfies F', so F' is not 3-admissible. Thus the reduction to acyclic formulas used in the upper-bound proof of Theorem 12 is unproven; a different argument is needed if the lemma's existence claim is true.
[§4, Lemma 14] The t-admissibility verification in Lemma 14 also appears to have a sign error. From an assignment alpha that falsifies the removed clause (x∨Y), we have alpha(x)=1 and alpha(Y)=0. For every added clause (Z∨Y) with Z in pred(x), satisfaction of F' then forces alpha(Z)=1, not alpha(Z)=0 as the proof states. The subsequent flip beta therefore does not obviously preserve satisfiability or the claimed weight inequality. As written, the monotonicity reduction needed for Theorem 12 is also not established.
[§1, Conjecture 2 and Related and Subsequent Works] Conjecture 2 is stated for every k>=2, but the later note in the same section states that [2] already showed Conjecture 2 is false for k=4. This is an internal inconsistency in the manuscript's main conjecture. The conjecture and the circuit-lower-bound consequence in Observation 5 should be reformulated, e.g., as a conjecture for odd k plus a suitably modified statement for even k, rather than presented without the known counterexample.

minor comments (4)

[Title and Abstract] The title contains a typo: 'ofk-CNF' should be 'of k-CNF'; the abstract also has a missing space before the sum in the definition of the threshold function.
[§3, Theorem 8] The uniqueness proof of Theorem 8 uses a stronger inductive claim than the one stated: it asserts that the weight-(t-1) satisfying assignments of F' are exactly the one-per-block assignments, but the induction hypothesis only says that an optimal formula contains t-1 disjoint clauses. Please make the strengthened induction hypothesis explicit.
[§4, Lemma 14] The description of the transformation in Lemma 14 is difficult to parse because the clause (x∨Y) does not correspond to an edge named (x,Y) in the implication graph as defined earlier; the notation pred(x), succ(Y), and the deleted edge should be defined precisely in terms of the implication graph.
[§1, Theorem 3] The informal Theorem 3 states only the case where b=1/(1-alpha) is an integer dividing n; Theorem 12 is the general and exact statement and should be advertised as the main k=2 result in the introduction.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's bounds are derived from independent external theorems (Song-Yao, Keevash, entropy bounds) and self-contained combinatorial arguments; self-citations are non-load-bearing.

full rationale

The derivation chain for the central result, Theorem 12, starts from the definition of S(n,t,k), proves lower bounds by explicit block constructions (Lemma 7, Lemma 9), and obtains the upper bound by transforming an optimal 2-CNF to a monotone acyclic one (Lemmas 13-14) and then invoking the independent Song-Yao theorem on maximal independent sets (Lemma 15). No parameter is fitted, no quantity is defined in terms of the quantity it is used to predict, and no load-bearing step is justified only by a self-citation. Theorem 17 is a genuine equivalence with the Turan problem rather than a renaming; the paper explicitly leaves the Turan value open. The only references to the authors' own subsequent work (e.g., [8]) appear in the 'Related and Subsequent Works' paragraph and are not used in any proof. A reader's note points to a possible gap in the t-admissibility argument of Lemma 13; even if that gap is real, it is a correctness or soundness concern about the proof machinery, not a circularity in which a claimed prediction reduces by construction to an input. Accordingly the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central results rest on three external theorems, none of which is proved in this paper: the Song-Yao bound on maximal independent sets, Keevash's design existence theorem, and standard entropy estimates. No free parameters are fitted to data, and no new postulated entities are introduced. The adaptive block construction is a combinatorial construction, not an invented entity requiring independent evidence.

assumptions (3)

domain assumption Song-Yao theorem: every n-vertex graph has at most q^{n-t-r}(q+1)^r maximal independent sets of size n-t, where n=(n-t)q+r.
Invoked as Lemma 15 to bound the number of maximal independent sets in the graph representation of a monotone 2-CNF formula. It is external to this paper and not proved here.
domain assumption Keevash's existence theorem for Steiner systems with constants r and q for sufficiently large n satisfying divisibility conditions.
Invoked in Corollary 22 to state exact values of S(n,t,k) when n-k and t are constants. The existence and construction of such designs is a deep external result.
standard math Standard entropy bounds for binomial coefficients, Lemma 6 (MacWilliams-Sloane).
Used in Proposition 11 to convert exact block-construction values into asymptotic circuit lower bounds. This is a routine, well-known estimate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Extremal Properties of k-CNF: Capturing Threshold Functions." pith.science (2026). https://pith.science/paper/GVXTC2HR

@misc{pith2026241220493,
  author       = {Pith},
  title        = {Pith review of: On Extremal Properties of k-CNF: Capturing Threshold Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GVXTC2HR}},
  note         = {Machine review of arXiv:2412.20493}
}

abstract

We consider a basic question on the expressiveness of $k$-CNF formulas: How well can $k$-CNF formulas capture threshold functions? Specifically, what is the largest number of assignments (of Hamming weight $t$) accepted by a $k$-CNF formula that only accepts assignments of weight at least $t$? Among others, we provide the following results: - While an optimal solution is known for $t \leq n/k$, the problem remains open for $t > n/k$. We formulate a (monotone) version of the problem as an extremal hypergraph problem and show that for $t = n-k$, the problem is exactly the Tur\'{a}n problem. - For $t = \alpha n$ with constant $\alpha$, we provide a construction and show its optimality for $2$-CNF. Optimality of the construction for $k>2$ would give improved lower bounds for depth-$3$ circuits.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[1977]

26 Nikhil Vyas and Ryan Williams

Springer Berlin Heidelberg. 26 Nikhil Vyas and Ryan Williams. On super strong eth. In Mikoláš Janota and Inês Lynce, editors, Theory and Applications of Satisfiability Testing – SAT 2019, pages 406–423, Cham,

work page 2019
[1984]

The composition complexity of majority

14 Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The composition complexity of majority. In Shachar Lovett, editor,37th Computational Complexity Conference, CCC 2022, M. Gurumukhani, M. Künnemann and R. Paturi 15 July 20-23, 2022, Philadelphia, PA, USA, volume 234 ofLIPIcs, pages 19:1–19:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2022
[1994]

Super strong ETH is true for PPSZ with small resolution width

20 Dominik Scheder and Navid Talebanfard. Super strong ETH is true for PPSZ with small resolution width. In Shubhangi Saraf, editor,35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 3:1–3:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2020
[1995]

Marques Silva and Inês Lynce

22 João P. Marques Silva and Inês Lynce. Towards robust CNF encodings of cardinality con- straints. In Christian Bessiere, editor,Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, volume 4741 ofLecture Notes in Computer Science, pages 483–497. Springer,

work page 2007
[2006]

A variant of the vc-dimension with applications to depth-3 circuits

6 Peter Frankl, Svyatoslav Gryaznov, and Navid Talebanfard. A variant of the vc-dimension with applications to depth-3 circuits. In Mark Braverman, editor,13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 ofLIPIcs, pages 72:1–72:19. Schloss Dagstuhl - Leibniz-Zentrum für In...

work page 2022
[2007]

Towards an optimal cnf encoding of boolean cardinality constraints

23 Carsten Sinz. Towards an optimal cnf encoding of boolean cardinality constraints. In Peter van Beek, editor,Principles and Practice of Constraint Programming - CP 2005, pages 827–831, Berlin, Heidelberg,

work page 2005
[2011]

The existence of designs.arXiv preprint arXiv:1401.3665,

12 Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665,

arXiv
[2014]

Klawe, Wolfgang J

13 Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, and Mihalis Yannakakis. On monotone formulae with restricted depth (preliminary version). In Richard A. DeMillo, editor,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 480–487. ACM,

work page 1984

Show all 15 references

[2016]

Depth-three circuits for inner product and majority functions

2 Kazuyuki Amano. Depth-three circuits for inner product and majority functions. In Satoru Iwata and Naonori Kakimura, editors,34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan, volume 283 ofLIPIcs, pages 7:1–7:16. Schloss...

2023
[2019]

27 Guy Wolfovitz

Springer International Publishing. 27 Guy Wolfovitz. The complexity of depth-3 circuits computing symmetric boolean functions. Information Processing Letters, 100(2):41–46, 2006

2006
[2020]

25 Leslie G

https://arxiv.org/abs/2012.06066. 25 Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Jozef Gruska, editor, Mathematical Foundations of Computer Science 1977, pages 162–176, Berlin, Heidelberg,

2012 arXiv
[2021]

Saks, and Navid Tale- banfard

8 Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Navid Tale- banfard. Local enumeration and majority lower bounds. In Rahul Santhanam, editor,39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA, volume 300 ofLIPIcs,...

2024
[2022]

Kulikov, and R

7 Alexander Golovnev, Alexander S. Kulikov, and R. Ryan Williams. Circuit depth reductions. In James R. Lee, editor,12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 ofLIPIcs, pages 24:1–24:20. Schloss Dag...

2021
[2023]

3 Ravi B. Boppana. Threshold functions and bounded depth monotone circuits. In Richard A. DeMillo, editor,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 475–479. ACM,

1984
[2024]

Fasterk-sat algorithms using biased-ppsz

9 Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Fasterk-sat algorithms using biased-ppsz. In Moses Charikar and Edith Cohen, editors,Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages ...

2019

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1977]

26 Nikhil Vyas and Ryan Williams

Springer Berlin Heidelberg. 26 Nikhil Vyas and Ryan Williams. On super strong eth. In Mikoláš Janota and Inês Lynce, editors, Theory and Applications of Satisfiability Testing – SAT 2019, pages 406–423, Cham,

work page 2019

[2] [1984]

The composition complexity of majority

14 Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The composition complexity of majority. In Shachar Lovett, editor,37th Computational Complexity Conference, CCC 2022, M. Gurumukhani, M. Künnemann and R. Paturi 15 July 20-23, 2022, Philadelphia, PA, USA, volume 234 ofLIPIcs, pages 19:1–19:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2022

[3] [1994]

Super strong ETH is true for PPSZ with small resolution width

20 Dominik Scheder and Navid Talebanfard. Super strong ETH is true for PPSZ with small resolution width. In Shubhangi Saraf, editor,35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 3:1–3:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2020

[4] [1995]

Marques Silva and Inês Lynce

22 João P. Marques Silva and Inês Lynce. Towards robust CNF encodings of cardinality con- straints. In Christian Bessiere, editor,Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, volume 4741 ofLecture Notes in Computer Science, pages 483–497. Springer,

work page 2007

[5] [2006]

A variant of the vc-dimension with applications to depth-3 circuits

6 Peter Frankl, Svyatoslav Gryaznov, and Navid Talebanfard. A variant of the vc-dimension with applications to depth-3 circuits. In Mark Braverman, editor,13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 ofLIPIcs, pages 72:1–72:19. Schloss Dagstuhl - Leibniz-Zentrum für In...

work page 2022

[6] [2007]

Towards an optimal cnf encoding of boolean cardinality constraints

23 Carsten Sinz. Towards an optimal cnf encoding of boolean cardinality constraints. In Peter van Beek, editor,Principles and Practice of Constraint Programming - CP 2005, pages 827–831, Berlin, Heidelberg,

work page 2005

[7] [2011]

The existence of designs.arXiv preprint arXiv:1401.3665,

12 Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665,

arXiv

[8] [2014]

Klawe, Wolfgang J

13 Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, and Mihalis Yannakakis. On monotone formulae with restricted depth (preliminary version). In Richard A. DeMillo, editor,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 480–487. ACM,

work page 1984