Zobrazeno 1 - 10
of 164
pro vyhledávání: '"03F20"'
Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distribution $P^A_{v}$ on $\mathbb{R}^n$ that behaves like a known distributi
Externí odkaz:
http://arxiv.org/abs/2410.21426
The function $p_{xy}$ that interchanges two logical variables $x,y$ in formulas is hard to describe in the following sense. Let $F$ denote the Lindenbaum-Tarski formula-algebra of a finite-variable first order logic, endowed with $p_{xy}$ as a unary
Externí odkaz:
http://arxiv.org/abs/2409.04088
Autor:
Lin, Tianrong
We prove in this paper that there is a language $L_d$ accepted by some nondeterministic Turing machines but not by any ${\rm co}\mathcal{NP}$-machines (defined later). Then we further show that $L_d$ is in $\mathcal{NP}$, thus proving that $\mathcal{
Externí odkaz:
http://arxiv.org/abs/2406.10476
Autor:
Japaridze, Giorgi
Cirquent calculus is a proof system with inherent ability to account for sharing subcomponents in logical expressions. Within its framework, this article constructs an axiomatization CL18 of the basic propositional fragment of computability logic the
Externí odkaz:
http://arxiv.org/abs/2406.05879
Autor:
Grochow, Joshua A.
The Ideal Proof System (IPS) of Grochow & Pitassi (FOCS 2014, J. ACM, 2018) is an algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable systems of polynomial equations. One potential drawback of IPS is that ve
Externí odkaz:
http://arxiv.org/abs/2306.02184
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or r
Externí odkaz:
http://arxiv.org/abs/2305.19320
In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simulation, i.e
Externí odkaz:
http://arxiv.org/abs/2304.09422
Autor:
Jeřábek, Emil
We present a streamlined and simplified exponential lower bound on the length of proofs in intuitionistic implicational logic, adapted to Gordeev and Haeusler's dag-like natural deduction.
Comment: 32 pages; mention effects of recent improved ci
Comment: 32 pages; mention effects of recent improved ci
Externí odkaz:
http://arxiv.org/abs/2303.15090
Autor:
Krajicek, Jan
Given a sound first-order p-time theory $T$ capable of formalizing syntax of first-order logic we define a p-time function $g_T$ that stretches all inputs by one bit and we use its properties to show that $T$ must be incomplete. We leave it as an ope
Externí odkaz:
http://arxiv.org/abs/2303.10637
Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultaneously falsified. [Peitl,Szeider,05] conjectured that hitting formulas
Externí odkaz:
http://arxiv.org/abs/2302.06241