r/compsci
▲ 1.2k r/compsci
All the complexity improvements released by OpenAI today
u/cringevampire — 8 days ago
▲ 0 r/compsci
Believing P≠NP is fundamentally an act of faith in a world that values the journey over the destination, a belief that the universe was designed to reward deep, grueling effort rather than making all truths instantly cheap
u/big_hole_energy — 4 days ago
▲ 10 r/compsci
Implementation of Andreas Bjorklund's algorithm for determining hamiltonicity
Hello, I want to share a project that i've been working on for the last month or so. It's and implementation (from what i could find the only rn on the internet) of Andreas Bjorklund's theoretical algorithm for determining weather a graph is hamiltonian or not. The algorithm is revolutionary because it lowered the exponential part of the time complexity of Held-Karp which is the standard algorithm for determining weather a graph is hamiltonian, from O^(2^n) to O^(1.657^n) for general graphs(this is what i've managed to implement as of right not) and for bipartite its O^*(1.414^n).
It might have some logical errors, and could maybe be optimised but right now, as of writting this it is 4AM and i want to sleep.
link to paper: https://arxiv.org/pdf/1008.0541
link to the github repo: https://github.com/Ak0-m/Bjorklunds\_algorithm\_for\_Hamiltonicity
u/Willy_Importance69 — 4 days ago
▲ 335 r/compsci
An algorithm for sub-quadratic 3SUM and sub-cubic APSP has been found
arxiv.orgu/azurerazor — 9 days ago
▲ 100 r/compsci
John Urschel 🏈 proves sqrt(n) growth factor for partial pivots
arxiv.orgu/beeskness420 — 8 days ago
▲ 26 r/compsci
Is lean, and similar programming languages the only acceptable way to prove theorem with computers?
So, lean is the language built specifically to prove theorems.but if the algorithm will be rewritten in another programming language, such as python, will it be accepted?
(mathematical theorems)
u/FollowingEvery4802 — 10 days ago
▲ 100 r/compsci
RuleFlow: A research engine/framework and terminal IDE (Not AI Slop)
Main Website: https://www.ruleflow.org/
For the past year, I have been developing a framework to simulate certain discrete systems for a research team at my university (paid for by the School of Engineering and Physics, but I had the freedom to license it under MIT). As it turns out, I got carried away generalizing it to work for many, many different types of complex systems (String Rewriting Systems, Cellular Automata, etc.) and ended up creating our own domain-specific language.
The website's landing page has a bunch of GIF-style examples... so you should be able to get a good idea of what this project is about.
If any of y'all are interested in this, feel free to take a look and try it out!
EDIT:
Out of the interest of not being "vague", here are some more details. RuleFlow was developed with a primary focus on analyzing causality in Sequential Substitution Systems. This is why there is a major focus on causal graphs, cellular identity, etc. While originally developed for Sequential Sub Systems, we generalized the DSL to support many types of rewriting systems by providing the user with flags and directives to control how rules behave. Furthermore, we bootstrapped Python and the Wolfram Language so that complex rulesets could be scaffolded as macros. The main goal of RuleFlow is NOT simply to simulate systems (there's already plenty of software for that, such as Golly and even just Mathematica), but to provide extensive tooling for causal analysis.
Here is some interesting research from our (small) team:
- An Improved Generalized Enumeration of Substitution Systems by Kenneth E. Caviness, Camille Morrow, Christen Case and Victoria Kratzke
- Indexed Concatenation Notation: A Novel Way to Summarize Networks and Other Complex Systems
My job has been to provide better research tooling, extending what we already have in Mathematica code to open source and free Python.
u/sciencenerd_1943 — 11 days ago
▲ 0 r/compsci
Capabilities of physics to go beyond Turing machine?
Quantum computes are believed to have higher capabilities than Turing machine, bringing question if our physics could allow for even better ways, like the main concern: does our physics allow practical NP-solvers?
I think about it for ~20 years and just worked with topLLMs on big review: https://zenodo.org/records/23125606 - would gladly discuss
u/jarekduda — 11 days ago
▲ 9 r/compsci
bloom filters and the math behind their false positive rate
I've been going deep on data structures lately and found bloom filters pretty intriguing. I made a short video on what a bloom filter is, how the bit array and hash functions interact, and where the false positive formula comes from.
link: https://youtu.be/nNv4ZTQp_s8?si=j52fIUBYaDcaps0_
I'd love feedback, especially if I got anything wrong. Happy to go through the derivation in the comments if anyone wants it.
u/Putrid-Ad-3768 — 9 days ago
▲ 6 r/compsci
Tiles-based video codec for videos of video games
Some video games, many of them are retro, are based on tiles. They have different levels which may be huge and logically highly complex but they are all based on limited sets of tiles.
Even a minute long video is usually bigger in file size than the retrog game itself.
It happens with Prince of Persia, Boulder Dash, Supaplex, Commander Keen, Bio Menace etc. - easier to recognize in two-dimensional games.
If video encoding used a database of tiles available in the game, it would enable much smaller file sizes and also higher quality of video as it would not have to use approximations to reduce file size as the tiles are exactly the same everywhere (meaning that lossless video would be affordable by bitrate). I am under no pressure to get it implemented ASAP but I would like a technological discussion about how-to.
u/Usual_Piano9826 — 13 days ago