theoretical-computer-science
awesome-theoretical-computer-science
Math & CS awesome List, distinguished by proof and logic technique
- 1.2k
- Python
- CC0-1.0
- 6 d ago
FormaleSysteme
Unterlagen zur Vorlesung "Formale Systeme", Fakultät Informatik, TU Dresden
- 51
- TeX
- 6 mo ago
TCSExam
A benchmark for the full range of theoretical computer science (TCS) research.
- 49
- Python
- Apache-2.0
- 10 d ago
TheoLog
Vorlesungsunterlagen "Theoretische Informatik und Logik", Fakultät Informatik, TU Dresden
- 28
- TeX
- 3 mo ago
integer-mult-kappa
Integer multiplication below n log n: a conditional witness kappa = 6685733/10^10 (> 2^-11) for T(n) = O(n (log n)^(1-kappa)) in the multitape model, building on OpenAI's problem and Colkitt's integer-mult-bounds: certificates, independent replays, Lean 4 checks
- 27
- Python
- Apache-2.0
- 6 wk ago
tcs-prover
Agentic TCS proof search with statement review, persistent authoring, independent criticism, and LaTeX editing.
- 18
- Python
- 7 d ago
theolog-ss2017
Notizen zur TheoLog-Vorlesung mit Begriffen aus Formale Systeme. Hinweis: die Unterlagen sind für die VL in 2017 und können Fehler enthalten
- 17
- TeX
- 9 y ago
tamesis-research-archive
Arquivo de pesquisa interdisciplinar do Laboratório Tamesis sobre informação, geometria, sistemas complexos e cognição, com distinção rigorosa entre hipóteses e evidências.
- 14
- Python
- 1 d ago
matrix_multiply_quadratic
This source code (in Python) is a preliminary implementation of my quadratic-time positive integer matrix multiplication.
- 12
- Python
- BSD-3-Clause
- 4 y ago
position-candidate-hypothesis-paradigm
Position-Candidate-Hypothesis (PCH) is a theoretical paradigm for structural-statistical analysis of NP-complete problems.
- 5
- TeX
- CC-BY-4.0
- 3 mo ago
mobius-x1
GF(2) Möbius / zeta transform in o(N log N) XOR gates, the first asymptotic improvement over Yates (1937) for circuits with cancellation: proofs, certificates, Lean 4 checks, and closed ideas. Asymptotic only, AI-checked, not yet human-refereed.
- 2
- C
- Apache-2.0
- 6 wk ago
threesum-derand
Deterministic 3SUM in O(n^1.995782) and APSP / (min,+) / all-edges Exact Triangle in O(n^2.995943), improving Alman–Vassilevska Williams: proofs, certificates, Lean 4 checks, and a list of closed ideas to avoid duplicate work
- 2
- Lean
- Apache-2.0
- 6 wk ago
Byzantine-Vector-Consensus
Theoretical analysis and algorithm development for Byzantine Vector Consensus in partially synchronous environments.
- 2
- 3 y ago
GameOfLifeALISP
Some work on the paper, "Automated Lie-algebraic input space partitioning using first-order two-dimensional cellular automata" by me (Shrohan Mohapatra. (2020, June 5). Automated Lie-algebraic input space partitioning using first-order two-dimensional cellular automata. Zenodo. http://doi.org/10.5281/zenodo.3880404), here in the specific example with Game of Life for automated Lie-algebraic input
- 2
- Mathematica
- 6 y ago
PACAGetMode
A Mathematica package by the name 'Polynomial adaptive cellular automata' to get the quasi-normal modes for the particles oscillating in the background of a black hole.
- 2
- Mathematica
- 7 y ago
PackMFCS
A set of python programs that can be used by early learners of the Mathematical Foundations of Computer Sciences (courtesy: Introduction to the Theory of Computation by Michael Sipser)
- 2
- Python
- 5 y ago
subsetsum-derand
Deterministic Subset Sum faster than meet-in-the-middle: 2^{0.4986298 n}, derandomising Ye–Li and OpenAI's 2^{0.49n} construction. Proofs, interval certificates, Lean 4 checks, and closed ideas. Preprint, not peer reviewed.
- 1
- Lean
- Apache-2.0
- 6 wk ago
LaunchpadACT
A series of programs that enable one's investigations in the algebraic complexity theory such as matrix multiplication algorithms, primality tests, algebraic complexity, sorting algorithms etc. Each algorithm is accompanied by a comparative time complexity analysis and a class of test cases and test suites.
- 1
- Mathematica
- 4 y ago
ProperEarleyParser-PEP
Design and implementation of a fast Earley parser with some test cases in Wolfram language ....... also a ready-made lexer with parsing with the grammar for all the regular languages :) :) ....
- 1
- Mathematica
- 6 y ago
-P-NP-Constructive-Proof-of-P-NP
This repository presents a constructive and complete proof of the P≠NP problem, based on structural separation and recursive unconstructibility. 本リポジトリは、構成的手法によりP≠NP問題を完全に証明した理論を収録しています。構成不能性と分離構造に基づく新たなアプローチです。
- 0
- 17 mo ago



