Blockchain Papers

Follow blockchain research across journals, conferences, and preprint repositories.

16 papersLast indexed Aug 31, 2026
Search papers

Paper index

16 results · page 1 of 1

Clear filters
May 24, 2026·Zenodo (CERN European Organization for Nuclear Research)
0 cites
Xenopoulos' Historical Genetic Logic: A New Framework and the XEPTQLRI Theorem

AKATERINH XENOPOULOU-TYROKOMOU, Epameinondas Xenopoulos

Xenopoulos’ Historical Genetic Logic: A New Framework and the XEPTQLRI Theorem DOI:10.5281/zenodo.20367121Date: May 2026 Aikaterini Xenopoulou TyrokomouIndependent ResearcherORCID: 0009 0004 9057 7432Email: katerinaxenopoulou@gmail.com Theoretical Foundation: Epameinondas Xenopoulos †Based on the Historical Genetic Logic of Epameinondas Xenopoulos, Epistemology of Logic: Logic Dialectic or Theory of Knowledge (posthumous 2nd ed., 2024) [1, 2]ORCID: 0009 0000 1736 8555† In memoriam (1920–1994) Methodological NoteThe present work simplifies and mathematizes central ideas of the formal-dialectical logic of E. Xenopoulos in order to create an applicable computational tool. It does not constitute a faithful rendering of his philosophical theory in its full depth, but a focused operationalization for the purpose of computational application. Statement of AuthorshipThe present work is founded on the logical system of Epameinondas Xenopoulos (1920–1994). The XEPTQLRI index does not constitute an independent theory, nor does it introduce a new autonomous logical framework. The theoretical background, the basic categories, the logical relations, the fundamental principles, and the dialectical operators belong to the work of Epameinondas Xenopoulos. The contribution of the present work consists in the formal mathematical operationalization of specific principles of this logical system through a computable index, capable of being applied to dynamic and historically evolving systems. Consequently, the theoretical authorship belongs entirely to Epameinondas Xenopoulos, while the present work belongs to the level of systematic formalization, proof, application, and methodological development of his framework. The XEPTQLRI index expresses in quantitative form the logic of Being, Non-Being, Becoming, historical memory, and dialectical sublation, while adapting these concepts for computational use. In this sense, the present work constitutes a continuation, clarification, and applicative deepening of the Xenopoulos system, not a displacement or replacement of it. ABSTRACT We present the Xenopoulos Pre-Transitional Qualitative Leap Risk Index (XEPTQLRI), a novel mathematical index grounded in the Historical-Genetic Logic of the Greek philosopher Epameinondas Xenopoulos [1, 2]. Unlike conventional statistical summaries, XEPTQLRI captures the dialectical interplay between Being (B), Non‑Being (N), historical memory (τ), and a historical paradox factor (Π). The index is defined as Ξ = [T · τ · (1 + Π)] / Θ₀ with Θ₀ = 0.85, where T = 2BN/(B+N) is the dialectical tension expressed through the harmonic mean. Its construction respects strict causality, min‑max or logistic normalization, and a negative feedback mechanism (∂σ/∂Ξ < 0) in its dynamical extensions, though the index itself remains exogenous and purely diagnostic. We prove five theorems establishing constructive computability, scale homogeneity, non‑preservation of dynamical structure, representation dependence, and linear‑time computability. Two additional theorems (non‑self‑inversion and logical phase transition) are proved within the extended framework of the 34 Principles. Numerical experiments with the Ferrari–Xenopoulos v4.0 stochastic model show reproducible and persistent exceedance of the Aufhebung threshold, with endogenous volatility remaining low (σ ≈ 0.058). An extreme parameter run (α₅ = 1.6, σ₁ = 1.0, Θ₀ = 0.0867) reaches Ξ = 16.1, demonstrating that the critical value is not a universal constant but a local, parameter‑dependent realization. A “Dialectical War” experiment (LSTM vs. Xenopoulos system under noise = 1.0) reveals a striking dissociation: technical performance (MAE = 0.1039, 67.1% improvement) coexists with universal dialectical risk (20/20 high‑risk steps, Ξ_max = 2.99, zero paradoxality and false stability). This dissociation is mathematically consistent, as MAE and Ξ are distinct functions measuring different aspects of system behavior (MAE ⇏ Ξ). A null model comparison confirms that this risk is structurally generated (AUC 0.949 vs. 0.501, p < 0.001), with ground truth defined by the condition Ξ(t) ≄ Θ₀ for at least three consecutive time steps and binary classification threshold optimized via the Youden index. A strictly endogenous application of the canonical XEPTQLRI index to 13 distinct COVID‑19 waves in Greece (JHU CSSE) yields early warnings 48–90 days in advance (mean 84.0 days) with a mean EWS Score of 0.785, successfully detecting 10 of 13 waves (76.9%). The system substantially outperforms a simple cases‑threshold baseline (mean EWS 0.42, 23.1% success) without any reliance on AUC or external classifiers. Beyond its diagnostic function, the XEPTQLRI framework demonstrates a transformative capacity: non‑dialectical codes exposed to the Xenopoulos environment undergo systematic improvement, with documented gains ranging from 52.3% to 95.65% across multiple independent experiments. A banking crisis application correctly identified Lehman Brothers (z=3.2, p<0.001) and Bear Stearns (z=2.9, p<0.01) two years before their collapse using only pre‑2006 data. A financial early warning application achieved statistically significant predictive correlations (r=0.29–0.44, p<0.001) with lead times of 10–77 days across S&P 500, VIX, Treasury yields, and Bitcoin. Two complete experimental protocols (XENO‑EXP‑2026‑002 and XENO‑EXP‑2026‑003) provide systematic, statistically significant evidence that the Xenopoulos System, when fully embedded in machine learning architectures, functions as an improvement catalyst with measurable economic value (ROI 63:1, break‑even 6 days). Thus, XEPTQLRI bridges formal dialectics with practical early warning systems, establishing a universal law of qualitative transition while keeping its numerical expression local and context‑dependent. The present system constitutes a proto‑formalized theoretical framework — a structured mathematical–dynamical system with axiomatic foundation (34 Principles), provable theorems (7 Theorems), and computational implementation (Ferrari–Xenopoulos v4.0, COVID‑19 application), whose applicative and transformative value has been verified on real data. The system is internally consistent under its stated principles, though its full formalization in the sense of a Hilbert‑style formal system remains a subject for future work. Keywords: XEPTQLRI, Historical‑Genetic Logic, dialectical logic, qualitative leap, Aufhebung, early warning systems, stochastic differential equations, LSTM, COVID‑19, proto‑formalized framework, non‑classical negation, harmonic mean, paradox factor, historical memory, dialectical transformation, financial crisis prediction, code optimization. Lead paragraph Complex dynamical systems often undergo sudden, qualitative transformations—critical transitions that are difficult to anticipate with conventional statistical tools. This paper introduces a new mathematical framework for detecting such transformations, grounded in the Historical‑Genetic Logic of the Greek philosopher Epameinondas Xenopoulos (1920–1994). The central contribution is the Xenopoulos Pre‑Transitional Qualitative Leap Risk Index (XEPTQLRI), defined as Ξ(t) = T(t) · τ(t) · (1 + Π(t)) / Θ₀, where T is the dialectical tension between Being and Non‑Being, τ captures historical memory, and Π encodes the accumulated paradox of extreme past states. The index is fully endogenous, requires no external training or classifiers, and is accompanied by a typology of ten dialectical stages (τ₀–τ₉). We prove five constructive theorems, validate the framework through stochastic simulations, and apply it to real COVID‑19 data from Greece. Across 13 epidemic waves, XEPTQLRI issued early warnings with an average lead time of 84.0 days and a mean Early Warning Score of 0.785, substantially outperforming a simple cases‑threshold baseline. The framework thus bridges formal dialectics with operational early warning capability, offering a new lens for the study of critical phenomena. Part I — Definition and Foundation of XEPTQLRI 1. Theoretical Foundation This section presents the fundamental principles underlying the Xenopoulos Pre-Transitional Qualitative Leap Risk Index (XEPTQLRI), as formulated in the Historical-Genetic Logic of the Greek philosopher Epameinondas Xenopoulos (1920–1994) [1, 2]. These principles constitute the axiomatic framework of the index and determine both its mathematical form and its interpretive function. XEPTQLRI is neither a simple numerical magnitude nor a mere statistical summary. Instead, it is defined as a complex historical-dialectical index that captures the relationship between Being, Non-Being, their dialectical tension, historical tendency, and the probability of transcending a critical threshold of transformation. The index is embedded within the broader system of 34 Principles as the 23rd Principle, expressed through the general dialectical operator: Ξ(t) = N[F₂₃(G₂₃)]. 1.1 Principle 5: Complementarity According to the theory [1, 2], Non-Being is not an independent quantity but the complement of Being. This relationship is expressed by Principle 5: N(t)=1−B(t)N(t)=1−B(t) This equation implies that: B(t)+N(t)=1B(t)+N(t)=1 Therefore, the two quantities B(t) and N(t) are complementary aspects of the same dynamic state. If B(t) expresses the degree of presence of Being, then N(t) expresses the degree of presence of Non-Being. From the same principle it immediately follows that it is impossible for both of the following to hold simultaneously: B(t)>0.8andN(t)>0.8B(t)>0.8andN(t)>0.8 because then we would have B(t) + N(t) > 1.6, in contradiction with B(t) + N(t) = 1. Important clarification: In Theorem 2 (Paradoxical Transcendence), the condition B > 0.8 ∧ N > 0.8 refers to a special paradoxical state where the usual complementarity is suspended due to the historical accumulation of contradictions. In this state, B and N are not understood as instantaneous values at

Open access
2 source records
Mathematical and Theoretical Analysis
Advanced Algebra and Logic
Logic, Reasoning, and Knowledge
Original source
Sep 9, 2025·arXiv (Cornell University)
0 cites
Families of self-inverse functions and dilogarithm identities

Lauri Alha

A machine-checked, sorry-free development in Lean 4 over Mathlib (about 1500 lines) that fills a gap in Mathlib — the dilogarithm Li2, which the library cites but does not define — and follows it into a quantum-mechanics problem. To the best of the author's knowledge, the first formalization in any proof assistant of: the real dilogarithm with Euler's reflection identity, Landen's transformation and the duplication formula; the golden-ratio ladder Li2(1/φ2) = π2/15 − ln2φ (derived from a 3×3 linear system, no five-term relation) and the Lee–Yang effective central charge c_eff = 2/5 (the simplest thermodynamic-Bethe-ansatz dilogarithm identity); the Clausen function Cl2 and Catalan's constant G = Cl2(π/2); the FejĂ©r–Jackson inequality; the bound Cl2(Ξ) ≄ sin(Ξ)/2 by an asymptotics-free Abel summation; and the Margolus–Levitin and (an L1 form of the) Mandelstam–Tamm quantum speed limits. These assemble into the title theorem: the weight-2 zeta state (populations proportional to 1/n2 on equally spaced energy levels) has infinite mean energy and infinite energy variance — so both textbook speed limits say nothing — yet never reaches a state orthogonal to itself, because its autocorrelation is (6/π2)·Li2(e−iΞ) and the dilogarithm has no zero on the unit circle. A clock with an unbounded energy budget that never ticks. Every identity is classical (Euler, Landen, Clausen, FejĂ©r, Jackson, Mandelstam–Tamm, Margolus–Levitin); the contribution is the machine-checked development and its assembly. Every named theorem depends only on the three standard axioms (propext, Classical.choice, Quot.sound). Formalized with AI assistance (Claude, Anthropic); the mathematics and all claims are the author's responsibility.

Open access
Advanced Mathematical Identities
Advanced Algebra and Logic
semigroups and automata theory
Original source
Aug 21, 2025·EPiC series in computing
0 cites
A Generic Zero-Knowledge Range Argument with Preprocessing

Yuki Sawai, Kyoichi Asano, Yohei Watanabe, Mitsugu Iwamoto

Range arguments are a type of zero-knowledge proofs that aim to prove that a prover's committed value falls within a specified range for a verifier. Previously, most range arguments were constructed based on the DLOG assumption, and hence, exponentiation operation is required for proof generation and verification. In addition, it is generally known that splitting a zero-knowledge proof protocol into a preprocessing phase and an online phase makes computation after fixing the input efficient. Still, such protocol has yet to be known for range arguments. This paper proposes an efficient range arguments protocol with a preprocessing phase. Our proposal takes a new approach by using arithmetic circuits to express the constraints that the prover must prove. The prover (resp. verifier) can generate (resp. verify) a part of proof based on multiplication and addition operations instead of exponentiation operations. Our range argument is a generic construction that does not rely on any particular mathematical assumptions, which enables us to construct a post-quantum range argument. The implementation evaluation shows that the total computation time for the prover and verifier in the online phase is efficient compared to Bulletproofs, one of the state-of-the-art range proofs. Especially, the prover computation is efficient.

Open access
Logic, Reasoning, and Knowledge
Advanced Algebra and Logic
Complexity and Algorithms in Graphs
Original source
Jul 24, 2025·IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences
1 cites
Card-Based Arithmetic Operations Using Integer Commitments and Their Application to Statistical Data Aggregation

Shun Odaka, Yuichi Komano

Card-based cryptography enables players to compute logical and arithmetic operations securely, such as bitwise AND and addition of integers. Several multiparty computation protocols and zero-knowledge proof protocols utilizing these secure computations have been developed as its applications. However, the realization of an efficient protocol for an arithmetic operation other than addition and subtraction remains an open problem. This paper proposes card-based protocols, based on integer commitment, for multiplication, division, and square root. Compared to general constructions for protocols for these operations based on binary integer commitment, the proposed protocols exhibit superior simplicity and efficiency. Furthermore, these protocols introduce novel applications for card-based cryptography to secure statistical data aggregation.

Open access
graph theory and CDMA systems
Bayesian Modeling and Causal Inference
Advanced Algebra and Logic
Original source
Apr 1, 2025·Proceedings of the ACM on Programming Languages
4 cites
Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge

John C. Kolesar, Shan Ali, Timos Antonopoulos, RuĆŸica Piskač

Zero-knowledge (ZK) protocols enable software developers to provide proofs of their programs’ correctness to other parties without revealing the programs themselves. Regular expressions are pervasive in real-world software, and zero-knowledge protocols have been developed in the past for the problem of checking whether an individual string appears in the language of a regular expression, but no existing protocol addresses the more complex PSPACE-complete problem of proving that two regular expressions are equivalent. We introduce CrĂȘpe , the first ZK protocol for encoding regular expression equivalence proofs and also the first ZK protocol to target a PSPACE-complete problem. CrĂȘpe uses a custom calculus of proof rules based on regular expression derivatives and coinduction, and we introduce a sound and complete algorithm for generating proofs in our format. We test CrĂȘpe on a suite of hundreds of regular expression equivalence proofs. CrĂȘpe can validate large proofs in only a few seconds each.

Open access
2 source records
semigroups and automata theory
Advanced Algebra and Logic
Computability, Logic, AI Algorithms
Original source
Aug 1, 2024·arXiv (Cornell University)
0 cites
A Zero-Knowledge Proof of Knowledge for Subgroup Distance Problem

Cansu Betin Onur

In this study, we introduce a novel zero-knowledge identification scheme based on the hardness of the subgroup distance problem in the Hamming metric. The proposed protocol, named Subgroup Distance Zero Knowledge Proof (SDZKP), employs a cryptographically secure pseudorandom number generator to mask secrets and utilizes a Stern-type algorithm to ensure robust security properties.

Open access
2 source records
Optimization and Search Problems
Advanced Algebra and Logic
cs.CR
Original source
Jun 10, 2024·DipĂČsit Digital de la Universitat de Barcelona (Universitat de Barcelona)
0 cites
A formal introduction to zero-knowledge proofs

Peso Vilella, Antonio

Treballs Finals de Grau de MatemĂ tiques, Facultat de MatemĂ tiques, Universitat de Barcelona, Any: 2024, Director: Bruno Mazorra i Luis Victor Dieulefait

Open access
Logic, programming, and type systems
Computability, Logic, AI Algorithms
Advanced Algebra and Logic
Original source
Dec 7, 2022·Foundations and TrendsŸ in Privacy and Security
58 cites
Proofs, Arguments, and Zero-Knowledge

Justin Thaler

Interactive proofs (IPs) and arguments are cryptographic protocols that enable an untrusted prover to provide a guarantee that it performed a requested computation correctly. Introduced in the 1980s, IPs and arguments represented a major conceptual expansion of what constitutes a “proof” that a statement is true. Traditionally, a proof is a static object that can be easily checked step-by-step for correctness. In contrast, IPs allow for interaction between prover and verifier, as well as a tiny but nonzero probability that an invalid proof passes verification. Arguments (but not IPs) even permit there to be “proofs” of false statements, so long as those “proofs” require exorbitant computational power to find. To an extent, these notions mimic in-person interactions that mathematicians use to convince each other that a claim is true, without going through the painstaking process of writing out and checking a traditional static proof. Celebrated theoretical results from the 1980s and 1990s such as IP = PSPACE and MIP = NEXP showed that, in principle, surprisingly complicated statements can be verified efficiently. What is more, any argument can in principle be transformed into one that is zero-knowledge, which means that proofs reveal no information other than their own validity. Zero-knowledge arguments have a myriad of applications in cryptography. Within the last decade, general-purpose zero-knowledge arguments have made the jump from theory to practice. This has opened new doors in the design of cryptographic systems, and generated additional insights into the power of IPs and arguments (zero-knowledge or otherwise). There are now no fewer than five promising approaches to designing efficient, general-purpose zero-knowledge arguments. This survey covers these approaches in a unified manner, emphasizing commonalities between them.

Open access
2 source records
Logic, Reasoning, and Knowledge
Logic, programming, and type systems
Advanced Algebra and Logic
Original source
Jan 1, 2022·IEEE Access
16 cites
Extension of Interaction Aggregation Operators for the Analysis of Cryptocurrency Market Under q-Rung Orthopair Fuzzy Hypersoft Set

Rana Muhammad Zulqarnain, Imran Siddique, Sayed M. Eldin, Shahid Hussain Gurmani

One of the substantial innovations achieved through digitalization is cryptocurrencies, also known as simulated or digital currencies, which have been deliberated in the modern era as a new platform particularly suitable for financiers. Several cryptocurrencies, such as Bitcoin, Ethereum, Binance Coin, and Tether, do not trust a dominant expert. The classification and conduction of insecurity and the confirmation of digital currencies complicate decision-making. q-rung orthopair fuzzy hypersoft sets are an emerging arena of research intended to report the confidential restrictions of q-rung orthopair fuzzy soft sets on multiparameter indefinite functions. Such a function maps a tuple of sub-parameters to a power set of the universe. It emphasizes allocating attributes to their corresponding sub-attribute values in disjoint sets. These structures sort it an innovative systematic tool for addressing the obstacles of hesitancy. The q-rung orthopair fuzzy hypersoft set (q-ROFHSS) expertly compacts with tentative and ambagious facts equated to the existing q- rung orthopair fuzzy soft set and Pythagorean fuzzy hypersoft set (PFHSS). It is the most compelling mode for enlarging imprecise data in decision-making (DM). This investigation’s ultimate impartiality is presenting interactional algebraic operational laws for q-ROFHSS. Furthermore, some interaction aggregation operators (AOs) have been anticipated via our proposed operational laws, such as q-rung orthopair fuzzy hypersoft interactive weighted average (q-ROFHSIWA) and q-rung orthopair fuzzy hypersoft interactive weighted geometric (q-ROFHSIWG) operators with their essential properties. In reality, a mathematical illustration of DM obstacles is pondered to substantiate the proven technique’s dominance. Based on the projected interaction AOs, robust multi-criteria group decision-making (MCGDM) design has been offered, which carries the most practical consequences associated with predominant MCGDM methods. The significance spectacle is that the intentional methodology is more operative and steady in bearing weird facts based on q-ROFHSS.

Open access
Multi-Criteria Decision Making
Fuzzy and Soft Set Theory
Advanced Algebra and Logic
Original source
Nov 29, 2021·Mathematical Structures in Computer Science
0 cites
A quantitative model for simply typed λ-calculus

Martin Hofmann, Jérémy Ledent

Abstract We use a simplified version of the framework of resource monoids , introduced by Dal Lago and Hofmann, to interpret simply typed λ-calculus with constants zero and successor. We then use this model to prove a simple quantitative result about bounding the size of the normal form of λ-terms. While the bound itself is already known, this is to our knowledge the first semantic proof of this fact. Our use of resource monoids differs from the other instances found in the literature, in that it measures the size of λ-terms rather than time complexity.

Open access
Logic, programming, and type systems
Logic, Reasoning, and Knowledge
Advanced Algebra and Logic
Original source
Sep 1, 2021·DOAJ (DOAJ: Directory of Open Access Journals)
0 cites
Generic Construction of Decentralized Attribute-Based ÎŁ-Protocol and Its Applications

Yang Xiaoli, Zhenjie Huang

Attribute-based cryptography becomes one of the hot topics in cryptography, since it can provide fine-grained access control and good privacy. ÎŁ-protocol is a 3-move public-coin honest verifier zero-knowledge proof protocol, and has important applications in many fields of cryptography. Firstly, combining the concept of attribute-based cryptography with the zero-knowledge proof, a notion of attribute-based ÎŁ-protocol is introduced with its formal security model. Secondly, based on the standard ÎŁ-protocol, the trapdoor samplable relation and the smooth secret sharing, a general construction of decentralized attribute-based ÎŁ-protocol and corresponding scheme are proposed with the proofs of its securities. Finally, as the applications of decentralized attribute-based ÎŁ-protocol, general constructions of decentralized attribute-based signature and decentralized attribute-based two-tier signature are presented by Fiat-Shamir transformation, respectively. Some concrete schemes are also presented. Performance analysis shows that the proposed attribute-based two-tier signature scheme has obvious advantages in both sizes and computation costs compared with existing schemes.

Open access
Advanced Algebra and Logic
Petri Nets in System Modeling
Logic, Reasoning, and Knowledge
Original source
Mar 19, 2019·Journal of Logic and Computation
15 cites
A temporal epistemic logic with a non-rigid set of agents for analyzing the blockchain protocol

Bojan Marinković, Paola Glavan, Zoran Ognjanović, Thomas Studer

Abstract In this paper we provide a strongly complete axiomatization of a temporal epistemic logic in which non-rigid sets of agents are allowed. Using this framework, we prove a number of properties of the blockchain protocol with respect to the given set of axioms and premises.

Open access
Logic, Reasoning, and Knowledge
Advanced Algebra and Logic
Logic, programming, and type systems
Original source
Mar 30, 2018·International Journal of System Modeling and Simulation
0 cites
Algebraic Verification Algorithm

Areej M. Abduldaim

Authentication over insecure public networks or with untrusted servers raises more concerns in privacy and security.Modern algebra is one of the significantfields of mathematics. It is a combination of techniques used for a variety of applications including the process of the manipulation of the mathematical categories. In addition,modern algebra deals in depth with the study of abstractions such as groups, rings and fields,the main objective of this article is to provide a novel algebraic verification protocol using ring theory. The protocol is blind, meaning that it detects only the identity, and no additional information will be known anything about the prover (the biometric) to the authenticating server or vice-versa. More officially a blind authentication scheme is a cryptographic protocol that comprises of two parties, a user (the prover) that wants to achieve having signs on her messages, and a signer (the verifier) that is in ownership of his secret signing key. In this paper, we employ the algebraic structure called central Armendariz rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is established and illustrated through numerical example, and its soundness and completeness are proved.This method gave two important properties for the central Armendariz zero knowledge protocol compared with other known protocols.

Open access
Computability, Logic, AI Algorithms
Advanced Algebra and Logic
Cryptography and Data Security
Original source
Mar 31, 2016·Foundations and TrendsŸ in Theoretical Computer Science
39 cites
Quantum Proofs

Thomas Vidick, John Watrous

Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.

Open access
Logic, Reasoning, and Knowledge
Logic, programming, and type systems
Advanced Algebra and Logic
Original source
Jan 1, 1998·Journal of Computer and System Sciences
10 cites
On the Limits of Nonapproximability of Lattice Problems

Oded Goldreich, Shafi Goldwasser

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), HĂ„stad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.

Open access
Logic, Reasoning, and Knowledge
Advanced Algebra and Logic
Semantic Web and Ontologies
Original source