Lower Bounds For Concurrent Zero Knowledge*

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.* An abridge version of this work has appeared in [24].     

A one-round,two-prover,zero-knowledge protocol for NP

The model of zero-knowledge multi-prover interactive proofs was introduced by Ben-Or, Goldwasser, Kilian and Wigderson in [4]. A major open problem associated with this model is whether NP problems can be proven by one-round, two-prover, zero-knowledge protocols with exponentially small error probability (e.g. via parallel executions). A positive answer was claimed by Fortnow, Rompel and Sipser in [12], but its proof was later shown to be flawed by Fortnow who demonstrated that the probability of cheating inn independent parallel rounds can be much higher than the probability of cheating inn independent sequential rounds (with exponential ratio between them). In this paper we solve this problem: We show a new one-round two-prover interactive proof for Graph Hamiltonicity, we prove that it is complete, sound and perfect zeroknowledge, and thus every problem in NP has a one-round two-prover interactive proof which is perfectly zero knowledge under no cryptographic assumptions. The main difficulty is in proving the soundness of our parallel protocol namely, proving that the probability of cheating in this one-round protocol is upper bounded by some exponentially low threshold. We prove that this probability is at most 1/2 ^n/9 (wheren is the number of parallel rounds), by translating the soundness problem into some extremal combinatorial problem, and then solving this new problem.     

The student experience of mathematical proof at university level

While proofs are central to university level mathematics courses, research indicates that some students may complete their degrees with an incomplete picture of what constitutes a proof and how proofs are developed. The paper sets out to review what is known of the student experience of mathematical proof at university level. In particular, some evidence is presented of the conceptions of mathematical proof that recent mathematics graduates bring to their postgraduate course to teach high school mathematics. Such evidence suggests that while the least well-qualified graduates may have the poorest grasp of mathematical proof, the most highly qualified may not necessarily have the richest form of subject matter knowledge needed for the most effective teaching. Some indication of the likely causes of this incomplete student perspective on proof are presented.     

Classroom sociomathematical norms for proof presentation in undergraduate in abstract algebra

This paper is a case study of the teaching of an undergraduate abstract algebra course with a particular focus on the manner in which the students presented proofs and the class engaged in a subsequent discussion of those proofs that included validating the work. This study describes norms for classroom work that include a set of norms that the presenter of a proof was responsible for enacting, including only using previously agreed upon results, as well as a separate set that the audience was to enact related to developing their understanding of the presented proof and validating the work. The study suggests that the students developed a sense of communal and individual responsibility for contributing to growing the body of mathematical knowledge known by the class, with an implied responsibility for knowing the already developed mathematics. Moreover, the behaviors that norms prompted the students to engage were those that literature suggests leads to increased comprehension of proofs.     

Counter-examples for refinement of conjectures and proofs in primary school mathematics

The purpose of this study is to explore how primary school students reexamine their conjectures and proofs when they confront counter-examples to the conjectures they have proved. In the case study, a pair of Japanese fifth graders thought that they had proved their primitive conjecture with manipulative objects (that is, they constructed an action proof), and then the author presented a counter-example to them. Confronting the counter-example functioned as a driving force for them to refine their conjectures and proofs. They understood the reason why their conjecture was false through their analysis of its proof and therefore could modify their primitive conjecture. They also identified the part of the proof which was applicable to the counter-example. This identification and their action proof were essential for their invention of a more comprehensive conjecture.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

A vector bundle proof of Poncelet’s closure theorem

There are few different proofs of the celebrated Poncelet closure theorem about polygons simultaneously inscribed in a smooth conic and circumscribed around another. We propose a new proof, based on the link between Schwarzenberger bundles and Poncelet curves.     

Randomized proofs in arithmetic

A randomized proof system for arithmetic is introduced. A proof of an arithmetical formula is defined as its derivation from the axioms of arithmetic by the standard rules of inference of arithmetic and also one more rule which we call the random substitution rule. Such proofs can be regarded as a special kind of interactive proof and, more exactly, as a special kind of the Arthur-Merlin proofs. The main result of the paper shows that a proof in arithmetic with the random substitution rule can be considerably shorter than an arithmetical proof of the same formula. Namely, there exists a set of formulas such that (i) these formulas are provable in arithmetic but, unless PSPACE=NP, do not have polynomially long proofs; (ii) these proofs have polynomially long proofs in arithmetic with random substitution (whatever random numbers appear) and the probability of error of these proofs is exponentially small. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 49–71. Translated by E. Ya. Dantsin.     

Tactics for Hierarchical Proof

There is something of a discontinuity at the heart of popular tactical theorem provers. Low-level, fully-checked mechanical proofs are large trees consisting of primitive logical inferences. Meanwhile, high-level human inputs are lexically structured formal texts which include tactics describing search procedures. The proof checking process maps from the high-level to low-level, but after that, explicit connections are usually lost. The lack of connection can make it difficult to understand the proof trees produced by successful tactic proofs, and difficult to debug faulty tactic proofs. We propose the use of hierarchical proofs, also known as hiproofs, to help bridge these levels. Hiproofs superimpose a labelled hierarchical nesting on an ordinary proof tree, abstracting from the underlying logic. The labels and nesting are used to describe the organisation of the proof, typically relating to its construction process. In this paper we introduce a foundational tactic language Hitac which constructs hiproofs in a generic setting. Hitac programs can be evaluated using a big-step or a small-step operational semantics. The big-step semantics captures the intended meaning, whereas the small-step semantics is closer to possible implementations and provides a unified notion of proof state. We prove that the semantics are equivalent and construct valid proofs. We also explain how to detect terms which are stuck in the small-step semantics, and how these suggest interaction points with debugging tools. Finally we show some typical examples of tactics, constructed using tactical combinators, in our language.     

Glivenko sequent classes in the light of structural proof theory

In 1968, Orevkov presented proofs of conservativity of classical over intuitionistic and minimal predicate logic with equality for seven classes of sequents, what are known as Glivenko classes. The proofs of these results, important in the literature on the constructive content of classical theories, have remained somehow cryptic. In this paper, direct proofs for more general extensions are given for each class by exploiting the structural properties of G3 sequent calculi; for five of the seven classes the results are strengthened to height-preserving statements, and it is further shown that the constructive and minimal proofs are identical in structure to the classical proof from which they are obtained.     

Theo: An interactive proof development system

This paper presents an interactive, tactic-driven, proof development system, a Theorem Prover calledTheo. Both the meta and the object levels of our theorem prover are logics presented in Typol. Typol is the programming language that implements Natural Semantics, a semantics developed at Inria and pioneered by G. Plotkin under the name Structural Operational Semantics. So Theo is written in Typol and helps the user to build proofs in an object logic also written in Typol. Tactics and tacticals are written in Typol. Other important features of Theo are the form chosen for representing proofs, and the way proofs are performed. The internal form of the proofs is very compact, expressed with combinators, that can be related to the -calculus used in Automath and its descendants. Meanwhile, Theo performs proofs by a pure calculus on proofs, using a resolution rule. Proofs may be incomplete and may contain logical variables. Theo is developed under the Centaur system, as well as Typol. This system provides a modern graphic man-machine interface that Theo uses, for the user's advantage.     

Combinatorial proofs and generalizations of conjectures related to Euler’s partition theorem

In a recent work, Andrews gave analytic proofs of two conjectures concerning some variations of two combinatorial identities between partitions of a positive integer into odd parts and partitions into distinct parts discovered by Beck. Subsequently, using the same method as Andrews, Chern presented the analytic proof of another Beck’s conjecture relating the gap-free partitions and distinct partitions with odd length. However, the combinatorial interpretations of these conjectures are still unclear and required. In this paper, motivated by Glaisher’s bijection, we give the combinatorial proofs of these three conjectures directly or by proving more generalized results.     

On transformations of constant depth propositional proofs

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.     

A Teacher's Conception of Communication in Geometry Proofs

Mathematical proof has many purposes, one of which is communication of the reasoning behind a mathematical insight. Research on teachers' views of the role that proof plays as mathematical communication has been limited. This study describes how one teacher conceptualized proof communication during two units on proof (coordinate geometry proofs and Euclidean proofs). Based on classroom observations, the teacher's conceptualization of communication in written proofs is recorded in four categories: audience, clarity, organization, and structure. The results indicate differences within all four categories in the way the idea of communication is discussed by the teacher. Implications for future studies include attention to teachers' beliefs about learning mathematics in the process of understanding teachers' conceptions of proof as a means of mathematical communication.     

矩阵对策鞍点定理的归纳法证明

Many proofs have been published for the minimax theorem, and all the published inductive proofs have been indirect ones. It has been pointed out that a direct inductive proof is needed, especially for instructional purposes, since indirect proofs are more or less implicit in nature. Such a direct proof is given in [4]. Now the minimax theorem can be stated equivalently in terms of saddle point; And it is the object of the present paper to give a direct inductive proof for the saddle point version of this theorem.     

Der invariante Kontinuitätssatz für meromorphe Funktionen

There are several proofs of the general version of the Kontinuitätssatz for meromorphic functions which is invariant under biholomorphic mappings. They are considerably more complicated than the proof of the analogous theorem for holomorphic functions. We present a method of proof which is as simple as the one for holomorphic functions and which allows to extend the theorem to infinite dimensions.     

A new proof for the correctness of the F5 algorithm

In 2002, Faugère presented the famous F5 algorithm for computing Gröbner basis where two criteria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness of the syzygy criterion, but the proof for the correctness of the rewritten criterion was left. Since then, F5 has been studied extensively. Some proofs for the correctness of F5 were proposed, but these proofs are valid only under some extra assumptions. In this paper, we give a proof for the correctness of F5B, an equivalent version of F5 in Buchberger’s style. The proof is valid for both homogeneous and non-homogeneous polynomial systems. Since this proof does not depend on the computing order of the S-pairs, any strategy of selecting S-pairs could be used in F5B or F5. Furthermore, we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.     

Indirect proof: what is specific to this way of proving?

The study presented in this paper is part of a wide research project concerning indirect proofs. Starting from the notion of mathematical theorem as the unity of a statement, a proof and a theory, a structural analysis of indirect proofs has been carried out. Such analysis leads to the production of a model to be used in the observation, analysis and interpretation of cognitive and didactical issues related to indirect proofs and indirect argumentations. Through the analysis of exemplar protocols, the paper discusses cognitive processes, outlining cognitive and didactical aspects of students’ difficulties with this way of proving.     

Geometric deduction of the solutions to modular equations

The Ramanujan Journal - In his notebooks, Ramanujan presented without proof many remarkable formulae for the solutions to generalized modular equations. Much later, proofs of the formulae were...