Computational Complexity

Mamba Meets Financial Markets: A Graph-Mamba Approach for Stock Price Prediction ArXiv ID: 2410.03707 “View on arXiv” Authors: Unknown Abstract Stock markets play an important role in the global economy, where accurate stock price predictions can lead to significant financial returns. While existing transformer-based models have outperformed long short-term memory networks and convolutional neural networks in financial time series prediction, their high computational complexity and memory requirements limit their practicality for real-time trading and long-sequence data processing. To address these challenges, we propose SAMBA, an innovative framework for stock return prediction that builds on the Mamba architecture and integrates graph neural networks. SAMBA achieves near-linear computational complexity by utilizing a bidirectional Mamba block to capture long-term dependencies in historical price data and employing adaptive graph convolution to model dependencies between daily stock features. Our experimental results demonstrate that SAMBA significantly outperforms state-of-the-art baseline models in prediction accuracy, maintaining low computational complexity. The code and datasets are available at github.com/Ali-Meh619/SAMBA. ...

Trading with Time Series Causal Discovery: An Empirical Study ArXiv ID: 2408.15846 “View on arXiv” Authors: Unknown Abstract This study investigates the application of causal discovery algorithms in equity markets, with a focus on their potential to build investment strategies. An investment strategy was developed based on the causal structures identified by these algorithms. The performance of the strategy is evaluated based on the profitability and effectiveness in stock markets. The results indicate that causal discovery algorithms can successfully uncover actionable causal relationships in large markets, leading to profitable investment outcomes. However, the research also identifies a critical challenge: the computational complexity and scalability of these algorithms when dealing with large datasets. This challenge presents practical limitations for their application in real-world market analysis. ...

Learning parameter dependence for Fourier-based option pricing with tensor trains ArXiv ID: 2405.00701 “View on arXiv” Authors: Unknown Abstract A long-standing issue in mathematical finance is the speed-up of option pricing, especially for multi-asset options. A recent study has proposed to use tensor train learning algorithms to speed up Fourier transform (FT)-based option pricing, utilizing the ability of tensor trains to compress high-dimensional tensors. Another usage of the tensor train is to compress functions, including their parameter dependence. Here, we propose a pricing method, where, by a tensor train learning algorithm, we build tensor trains that approximate functions appearing in FT-based option pricing with their parameter dependence and efficiently calculate the option price for the varying input parameters. As a benchmark test, we run the proposed method to price a multi-asset option for the various values of volatilities and present asset prices. We show that, in the tested cases involving up to 11 assets, the proposed method outperforms Monte Carlo-based option pricing with $10^6$ paths in terms of computational complexity while keeping better accuracy. ...

Markets are Efficient if and Only if P = NP ArXiv ID: ssrn-1773169 “View on arXiv” Authors: Unknown Abstract I prove that if markets are efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational p Keywords: Market Efficiency Hypothesis, Computational Complexity, Algorithmic Trading, P vs NP Problem, Informational Efficiency, Equities Complexity vs Empirical Score Math Complexity: 8.5/10 Empirical Rigor: 1.0/10 Quadrant: Lab Rats Why: The paper presents a formal theoretical proof linking market efficiency to computational complexity classes (P vs NP), requiring advanced mathematical reasoning and abstract computer science concepts. However, it contains no actual data, backtests, or implementation details; the empirical part is a brief illustrative example rather than rigorous analysis. flowchart TD A["Research Goal: Are Markets Efficient?"] B["Key Methodology: Complexity Theoretic Proof"] C["Input: Historical Price Data & Market Efficiency Assumption"] D["Computational Process: Reducing Market Arbitrage to NP-Hard Problem"] E["Key Finding: Market Efficiency Implies P = NP"] F["Implication: If P ≠ NP, Markets are Not Fully Efficient"] A --> B B --> C C --> D D --> E E --> F