Search

We investigate the cyclic proof theory of extensions of Peano Arithmetic by (finitely iterated) inductive definitions. Such theories are essential to proof theoretic analyses of certain "impredicative" theories; moreover, our cyclic systems naturally subsume Simpson’s Cyclic Arithmetic. Our main result is that cyclic and inductive systems for arithmetical inductive definitions are equally powerful. We conduct a metamathematical argument, formalising the soundness of cyclic proofs within second-order arithmetic by a form of induction on closure ordinals, thence appealing to conservativity results. This approach is inspired by those of Simpson and Das for Cyclic Arithmetic, however we must further address a difficulty: the closure ordinals of our inductive definitions (around Church-Kleene) far exceed the proof theoretic ordinal of the appropriate metatheory (around Bachmann-Howard), so explicit induction on their notations is not possible. For this reason, we rather rely on formalisation of the theory of (recursive) ordinals within second-order arithmetic., LIPIcs, Vol. 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023), pages 27:1-27:18

A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.

We study the computational expressivity of proof systems with fixed point operators, within the `proofs-as-programs' paradigm. We start with a calculus $\mu\mathsf{LJ}$ (due to Clairambault) that extends intuitionistic logic by least and greatest positive fixed points. Based in the sequent calculus, $\mu\mathsf{LJ}$ admits a standard extension to a `circular' calculus $\mathsf{C}\mu\mathsf{LJ}$. Our main result is that, perhaps surprisingly, both $\mu\mathsf{LJ}$ and $\mathsf{C}\mu\mathsf{LJ}$ represent the same first-order functions: those provably total in $\Pi^1_2$-$\mathsf{CA}_0$, a subsystem of second-order arithmetic beyond the `big five' of reverse mathematics and one of the strongest theories for which we have an ordinal analysis (due to Rathjen). This solves various questions in the literature on the computational strength of (circular) proof systems with fixed points. For the lower bound we give a realisability interpretation from an extension of Peano Arithmetic by fixed points that has been shown to be arithmetically equivalent to $\Pi^1_2$-$\mathsf{CA}_0$ (due to M\"ollerfeld). For the upper bound we construct a novel computability model in order to give a totality argument for circular proofs with fixed points. In fact we formalise this argument itself within $\Pi^1_2$-$\mathsf{CA}_0$ in order to obtain the tight bounds we are after. Along the way we develop some novel reverse mathematics for the Knaster-Tarski fixed point theorem.

Misinformation during pandemic situations like COVID-19 is growing rapidly on social media and other platforms. This expeditious growth of misinformation creates adverse effects on the people living in the society. Researchers are trying their best to mitigate this problem using different approaches based on Machine Learning (ML), Deep Learning (DL), and Natural Language Processing (NLP). This survey aims to study different approaches of misinformation detection on COVID-19 in recent literature to help the researchers in this domain. More specifically, we review the different methods used for COVID-19 misinformation detection in their research with an overview of data pre-processing and feature extraction methods to get a better understanding of their work. We also summarize the existing datasets which can be used for further research. Finally, we discuss the limitations of the existing methods and highlight some potential future research directions along this dimension to combat the spreading of misinformation during a pandemic., 43 pages, 6 figures

We investigate the proof complexity of systems based on positive branching programs, i.e. non-deterministic branching programs (NBPs) where, for any 0-transition between two nodes, there is also a 1-transition. Positive NBPs compute monotone Boolean functions, just like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than P or NC1, respectively. The proof complexity of NBPs was investigated in previous work by Buss, Das and Knop, using extension variables to represent the dag-structure, over a language of (non-deterministic) decision trees, yielding the system eLNDT. Our system eLNDT+ is obtained by restricting their systems to a positive syntax, similarly to how the 'monotone sequent calculus' MLK is obtained from the usual sequent calculus LK by restricting to negation-free formulas. Our main result is that eLNDT+ polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK by Atserias, Galesi and Pudl\'ak, that was recently improved to a bona fide polynomial simulation via works of Je\v{r}\'abek and Buss, Kabanets, Kolokolova and Kouck\'y. Along the way we formalise several properties of counting functions within eLNDT+ by polynomial-size proofs and, as a case study, give explicit polynomial-size poofs of the propositional pigeonhole principle., Comment: 31 pages, 5 figures

Objectives: Objectives: SARS-CoV-2 virus dynamics in the human body and its correlation with disease severity and biomarkers have not been elucidated. This study aims to evaluate the viral load in the blood sample of COVID-19 patients and viral load association with disease severity and progression.Methods: Blood samples from COVID-19 positive inpatients were collected sequentially, at admission, and during hospitalization. Depending on the clinical presentation, the patients were classified into mild, moderate, and severe categories. The blood samples were subjected to SARS-CoV-2 Real-time polymerase chain reaction (RT-PCR); positive samples were then tested for viral load using digital drop RT-PCR. Patients were followed up until they were discharged.Results: Of 83 enrolled patients, 15 (18.1%) were mild, 45 (54%) were moderate, and 23 (27.7%) had severe symptoms. The blood PCR in 21 patients was positive (rate was 25.3); one was mild, four moderate, and 16 severe on the day of admission. The mean cycle threshold (CT) of RNAemia in these 21 patients was 24.7+3.1. The viral load was significantly higher in patients with severe symptoms than others. Serum ferritin, D-dimer, and plasma fibrinogen were found raised along with lymphopenia in all patients. Viremia was found persistently detectable (or even rising) in patients in the severe category and associated with a fatal outcome.Conclusion: A prolonged elevation of D-dimer, serum ferritin, and plasma fibrinogen together with lymphopenia lead to a greater risk of mortality and morbidity. Quantitative estimation of virus in blood has a clinical significance which may help in prognostication and management of patients of COVID-19. J Microbiol Infect Dis 2021; 11(3):116-123.

Circular and non-wellfounded proofs have become an increasingly popular tool for metalogical treatments of systems with forms of induction and/or recursion. In this work we investigate the expressivity of a variant CT of G\"odel's system T where programs are circularly typed, rather than including an explicit recursion combinator. In particular, we examine the abstraction complexity (i.e. type level) of C, and show that the G\"odel primitive recursive functionals may be typed more succinctly with circular derivations, using types precisely one level lower than in T. In fact we give a logical correspondence between the two settings, interpreting the quantifier-free type 1 theory of level n+1 T into that of level n C and vice-versa. We also obtain some further results and perspectives on circular 'derivations', namely strong normalisation and confluence, models based on hereditary computable functionals, continuity at type 2, and a translation to terms of $\T$ computing the same functional, at all types., Comment: 74 pages, 9 figures

Logical Methods in Computer Science ; Volume 16, Issue 4 ; 1860-5974, This paper presents a complete axiomatization of Monadic Second-Order Logic (MSO) over infinite trees. MSO on infinite trees is a rich system, and its decidability ("Rabin's Tree Theorem") is one of the most powerful known results concerning the decidability of logics. By a complete axiomatization we mean a complete deduction system with a polynomial-time recognizable set of axioms. By naive enumeration of formal derivations, this formally gives a proof of Rabin's Tree Theorem. The deduction system consists of the usual rules for second-order logic seen as two-sorted first-order logic, together with the natural adaptation In addition, it contains an axiom scheme expressing the (positional) determinacy of certain parity games. The main difficulty resides in the limited expressive power of the language of MSO. We actually devise an extension of MSO, called Functional (Monadic) Second-Order Logic (FSO), which allows us to uniformly manipulate (hereditarily) finite sets and corresponding labeled trees, and whose language allows for higher abstraction than that of MSO.

We propose a graph-based extension of Boolean logic called Boolean Graph Logic (BGL). Construing formula trees as the cotrees of cographs, we may state semantic notions such as evaluation and entailment in purely graph-theoretic terms, whence we recover the definition of BGL. Naturally, it is conservative over usual Boolean logic. Our contributions are the following: (1) We give a natural semantics of BGL based on Boolean relations, i.e. it is a multivalued semantics, and show adequacy of this semantics for the corresponding notions of entailment. (2) We show that the complexity of evaluation is NP-complete for arbitrary graphs (as opposed to ALOGTIME-complete for formulas), while entailment is $\Pi^p_2$-complete (as opposed to coNP-complete for formulas). (3) We give a 'recursive' algorithm for evaluation by induction on the modular decomposition of graphs. (Though this is not polynomial-time, cf. point (2) above). (4) We characterise evaluation in a game-theoretic setting, in terms of both static and sequentical strategies, extending the classical notion of positional game forms beyond cographs. (5) We give an axiomatisation of BGL, inspired by deep-inference proof theory, and show soundness and completeness for the corresponding notions of entailment. One particular feature of the graph-theoretic setting is that it escapes certain no-go theorems such as a recent result of Das and Strassburger, that there is no linear axiomatisation of the linear fragment of Boolean logic (equivalently the multiplicative fragment of Japaridze's Computability Logic or Blass' game semantics for Mutliplicative Linear Logic)., Comment: 47 pages, 2 figures, 2 tables

Keynes argued that the short-term interest rate is the main driver of the long-term interest rate. This paper empirically models the relationship between short-term interest rates and long-term government securities yields in Canada, after controlling for other important financial variables. The statistical analysis uses high-frequency daily data from 1990 to 2018. It applies both the cointegration technique and Granger causality within the vector error correction (VEC) framework. The empirical results suggest that the action of the monetary authority is an important determinant of Canadian government securities yields, which supports the Keynesian perspective. These findings have important implications for investors, financial analysts, and policymakers.

This paper studies propositional proof systems in which lines are sequents of decision trees or branching programs - deterministic and nondeterministic. The systems LDT and LNDT are propositional proof systems in which lines represent deterministic or non-deterministic decision trees. Branching programs are modeled as decision dags. Adding extension to LDT and LNDT gives systems eLDT and eLNDT in which lines represent deterministic and non-deterministic branching programs, respectively. Deterministic and non-deterministic branching programs correspond to log-space (L) and nondeterministic log-space (NL). Thus the systems eLDT and eLNDT are propositional proof systems that reason with (nonuniform) L and NL properties. The main results of the paper are simulation and non-simulation results for tree-like and dag-like proofs in the systems LDT, LNDT, eLDT, and eLNDT. These systems are also compared with Frege systems, constantdepth Frege systems and extended Frege systems, 36 pages, 1 figure, full version of CSL 2020 paper

Peutz-Jeghers syndrome (PJS) is characterized by multiple hamartomatous polyps in the gastrointestinal tract and mucocutaneous pigmentation. Here we present, a case of multiple gastrointestinal hamartomatous polyps in a 22-year-old male who had been operated for intestinal obstruction due to ileocolic intussusception. Resection of the affected segment was done with proximal ileostomy and distal mucous fistula formation. Clinicopathological diagnosis of PJS was made. Later, during ileostomy closure, it was found that the patient had a transverse colonic mass which was resected. Histological examination with immunohistochemistry confirmed it to be a Mucosa-Associated Lymphoid Tissue Lymphoma (MALToma). Colonic MALToma in the background of PJS is a unique case for which it has been reported.

In this work we investigate how to extract alternating time bounds from 'focussed' proof systems. Our main result is the obtention of fragments of MALLw (MALL with weakening) complete for each level of the polynomial hierarchy. In one direction we encode QBF satisfiability and in the other we encode focussed proof search, and we show that the composition of the two encodings preserves quantifier alternation, yielding the required result. By carefully composing with well-known embeddings of MALLw into MALL, we obtain a similar delineation of MALL formulas, again carving out fragments complete for each level of the polynomial hierarchy. This refines the well-known results that both MALLw and MALL are PSPACE-complete. A key insight is that we have to refine the usual presentation of focussing to account for deterministic computations in proof search, which correspond to invertible rules that do not branch. This is so that we may more faithfully associate phases of focussed proof search to their alternating time complexity. This presentation seems to uncover further dualities at the level of proof search than usual presentations, so could be of further proof theoretic interest in its own right., 25 pages, 5 figures. Extended version of IJCAR '18 paper

This paper analyzes the dynamics of long-term US Treasury security yields from a Keynesian perspective using daily data. Keynes held that the short-term interest rate is the main driver of the long-term interest rate. In this paper, the daily changes in long-term Treasury security yields are empirically modeled as a function of the daily changes in the short-term interest rate and other important financial variables to test Keynes's hypothesis. The use of daily data provides a long time series. It enables the extension of earlier Keynesian models of Treasury security yields that relied on quarterly and monthly data. Models based on higher-frequency daily data from financial markets-such as the ones presented in this paper-can be valuable to investors, financial analysts, and policymakers because they make it possible for a real-time fundamental assessment of the daily changes in long-term Treasury security yields based on a wide range of financial variables from a Keynesian perspective. The empirical findings of this paper support Keynes's view by showing that the daily changes in the short-term interest rate are the main driver of the daily changes in the long-term interest rate on Treasury securities. Other financial variables, such as the daily changes in implied volatility of equity prices and the daily changes in the exchange rate, are found to have some influence on Treasury yields.

Logical Methods in Computer Science ; Volume 16, Issue 1 ; 1860-5974, We study the logical complexity of proofs in cyclic arithmetic ($\mathsf{CA}$), as introduced in Simpson '17, in terms of quantifier alternations of formulae occurring. Writing $C\Sigma_n$ for (the logical consequences of) cyclic proofs containing only $\Sigma_n$ formulae, our main result is that $I\Sigma_{n+1}$ and $C\Sigma_n$ prove the same $\Pi_{n+1}$ theorems, for all $n\geq 0$. Furthermore, due to the 'uniformity' of our method, we also show that $\mathsf{CA}$ and Peano Arithmetic ($\mathsf{PA}$) proofs of the same theorem differ only exponentially in size. The inclusion $I\Sigma_{n+1} \subseteq C\Sigma_n$ is obtained by proof theoretic techniques, relying on normal forms and structural manipulations of $\mathsf{PA}$ proofs. It improves upon the natural result that $I\Sigma_n$ is contained in $C\Sigma_n$. The converse inclusion, $C\Sigma_n \subseteq I\Sigma_{n+1}$, is obtained by calibrating the approach of Simpson '17 with recent results on the reverse mathematics of B\"uchi's theorem in Ko{\l}odziejczyk, Michalewski, Pradic & Skrzypczak '16 (KMPS'16), and specialising to the case of cyclic proofs. These results improve upon the bounds on proof complexity and logical complexity implicit in Simpson '17 and also an alternative approach due to Berardi & Tatsuta '17. The uniformity of our method also allows us to recover a metamathematical account of fragments of $\mathsf{CA}$; in particular we show that, for $n\geq 0$, the consistency of $C\Sigma_n$ is provable in $I\Sigma_{n+2}$ but not $I\Sigma_{n+1}$. As a result, we show that certain versions of McNaughton's theorem (the determinisation of $\omega$-word automata) are not provable in $\mathsf{RCA}_0$, partially resolving an open problem from KMPS '16.

The short-term interest rate is the main driver of the Commonwealth of Australia government bonds' nominal yields. This paper empirically models the dynamics of government bonds' nominal yields using the autoregressive distributed lag (ARDL) approach. Keynes held that the central bank exerts decisive influence on government bond yields because the central bank's policy rate and other monetary policy actions determine the short-term interest rate, which in turn affects long-term government bonds' nominal yields. The models estimated here show that Keynes's conjecture applies in the case of Australian government bonds' nominal yields. Furthermore, the effect of the budget balance ratio on government bond yields is small but statistically significant. However, there is no statistically discernable effect of the debt ratio on government bond yields.

This paper investigates the long-term determinants of Indian government bonds' (IGB) nominal yields. It examines whether John Maynard Keynes's supposition that short-term interest rates are the key driver of long-term government bond yields holds over the long-run horizon, after controlling for various key economic factors such as inflationary pressure and measures of economic activity. It also appraises whether the government finance variable-the ratio of government debt to nominal income-has an adverse effect on government bond yields over a long-run horizon. The models estimated here show that in India, short-term interest rates are the key driver of long-term government bond yields over the long run. However, the ratio of government debt and nominal income does not have any discernible adverse effect on yields over a long-run horizon. These findings will help policymakers in India (and elsewhere) to use information on the current trend in short-term interest rates, the federal fiscal balance, and other key macro variables to form their long-term outlook on IGB yields, and to understand the implications of the government's fiscal stance on the government bond market.

Quadricuspid aortic valve (QAV) is a rare congenital anomaly frequently associated with other anomalies particularly coronary anomalies. It may be detected on transthoracic or transesophageal echocardiography. We present here a case report of a 27-year-old male patient with a QAV, the valve being regurgitant and requiring aortic valve replacement. It has been reported as isolated case reports in the literature and various theories exist to the development of QAV. The diagnosis requires a high degree of suspicion and a detailed assessment, and if asymptomatic, then patients need to be carefully followed up for the development of aortic regurgitation.

Advertisers are increasingly turning to fingerprinting techniques to track users across the web. As web browsing activity shifts to mobile platforms, traditional browser fingerprinting techniques become less effective; however, device fingerprinting using built-in sensors offers a new avenue for attack. We study the feasibility of using motion sensors to perform device fingerprinting at scale, and explore countermeasures that can be used to protect privacy. We perform a large-scale user study to demonstrate that motion sensor fingerprinting is effective with even 500 users. We also develop a model to estimate prediction accuracy for larger user populations; our model provides a conservative estimate of at least 12% classification accuracy with 100000 users. We then investigate the use of motion sensors on the web and find, distressingly, that many sites send motion sensor data to servers for storage and analysis, paving the way to potential fingerprinting. Finally, we consider the problem of developing fingerprinting countermeasures; we evaluate a previously proposed obfuscation technique and a newly developed quantization technique via a user study. We find that both techniques are able to drastically reduce fingerprinting accuracy without significantly impacting the utility of the sensors in web applications.

Modern smartphones contain motion sensors, such as accelerometers and gyroscopes. These sensors have many useful applications; however, they can also be used to uniquely identify a phone by measuring anomalies in the signals, which are a result from manufacturing imperfections. Such measurements can be conducted surreptitiously in the browser and can be used to track users across applications, websites, and visits. We analyze techniques to mitigate such device fingerprinting either by calibrating the sensors to eliminate the signal anomalies, or by adding noise that obfuscates the anomalies. To do this, we first develop a highly accurate fingerprinting mechanism that combines multiple motion sensors and makes use of (inaudible) audio stimulation to improve detection. We then collect measurements from a large collection of smartphones and evaluate the impact of calibration and obfuscation techniques on the classifier accuracy.

John Maynard Keynes held that the central bank's actions determine long-term interest rates through short-term interest rates and various monetary policy measures. His conjectures about the determinants of long-term interest rates were made in the context of advanced capitalist economies, and were based on his views on ontological uncertainty and the formation of investors' expectations. Are these conjectures valid in emerging markets, such as India? This paper empirically investigates the determinants of changes in Indian government bonds' nominal yields. Changes in short-term interest rates, after controlling for other crucial variables such as changes in the rates of inflation and economic activity, take a lead role in driving changes in the nominal yields of Indian government bonds. This vindicates Keynes's theories, and suggests that his views on long-term interest rates are also applicable to emerging markets. Higher fiscal deficits do not appear to raise government bond yields in India. It is further argued that Keynes's conjectures about investors' outlooks, views, and expectations are fairly robust in a world of ontological uncertainty.

During the past two decades of economic stagnation and persistent deflation in Japan, chronic fiscal deficits have led to elevated and rising ratios of government debt to nominal GDP. Nevertheless, long-term Japanese government bonds' (JGBs) nominal yields initially declined and have stayed remarkably low and stable since then. This is contrary to the received wisdom of the existing literature, which holds that higher government deficits and indebtedness shall exert upward pressures on government bonds' nominal yields. This paper seeks to understand the determinants of JGBs' nominal yields. It examines the relationship between JGBs' nominal yields and short-term interest rates and other relevant factors, such as low inflation and persistent deflationary pressures and tepid growth. Low short-term interest rates, induced by monetary policy, have been the main reason for JGBs' low nominal yields. It is also argued that Japan has monetary sovereignty, which gives the government of Japan the ability to meet its debt obligations. It enables the Bank of Japan to exert downward pressure on JGBs' nominal yields by allowing it to keep short-term interest rates low and to use other tools of monetary policy. The argument that current short-term interest rates and monetary policy are the primary drivers of long-term interest rates follows Keynes's (1930) insights.

Background: Nosocomial infections are on the rise worldwide and many a times they are carried by the health care personnel. Accessories used by physicians and healthcare personnel can be a potential source of nosocomial infection. Materials and Methods: We designed a survey with the aim to investigate the prevalence of microbial flora of accessories such as pens, stethoscopes, cell phones and white coat used by the physicians working in a tertiary care hospital. Observations: It was observed that 66% of the pens, 55% of the stethoscopes, 47.61% of the cell phones and 28.46% of the white coats used by the doctors were colonized with various microorganisms. Staphylococcus spp. was the predominant isolate followed by Escherichia coli. Methicillin resistance in Staphylococcus aureus was also found, which was a matter of concern. Conclusions: Awareness of appropriate hand hygiene is important in order to prevent potential transmission to patients.