r/compsci • • Jun 16 '19

PSA: This is not r/Programming. Quick Clarification on the guidelines

646 Upvotes

As there's been recently quite the number of rule-breaking posts slipping by, I felt clarifying on a handful of key points would help out a bit (especially as most people use New.Reddit/Mobile, where the FAQ/sidebar isn't visible)

First thing is first, this is not a programming specific subreddit! If the post is a better fit for r/Programming or r/LearnProgramming, that's exactly where it's supposed to be posted in. Unless it involves some aspects of AI/CS, it's relatively better off somewhere else.

r/ProgrammerHumor: Have a meme or joke relating to CS/Programming that you'd like to share with others? Head over to r/ProgrammerHumor, please.

r/AskComputerScience: Have a genuine question in relation to CS that isn't directly asking for homework/assignment help nor someone to do it for you? Head over to r/AskComputerScience.

r/CsMajors: Have a question in relation to CS academia (such as "Should I take CS70 or CS61A?" "Should I go to X or X uni, which has a better CS program?"), head over to r/csMajors.

r/CsCareerQuestions: Have a question in regards to jobs/career in the CS job market? Head on over to to r/cscareerquestions. (or r/careerguidance if it's slightly too broad for it)

r/SuggestALaptop: Just getting into the field or starting uni and don't know what laptop you should buy for programming? Head over to r/SuggestALaptop

r/CompSci: Have a post that you'd like to share with the community and have a civil discussion that is in relation to the field of computer science (that doesn't break any of the rules), r/CompSci is the right place for you.

And finally, this community will not do your assignments for you. Asking questions directly relating to your homework or hell, copying and pasting the entire question into the post, will not be allowed.

I'll be working on the redesign since it's been relatively untouched, and that's what most of the traffic these days see. That's about it, if you have any questions, feel free to ask them here!


r/compsci • • 5h ago

Designing my own SRAM like it's 1969

8 Upvotes

I've been going down the rabbit hole lately trying to figure out how to design a computer from scratch using only electronic components and logic gates.

One thing that bothered me was how most explanations go from "transistors are just switches" to "here's how an ALU works, good luck", casually skipping the most interesting question: how is memory implemented ?

So I decided to work it out from first principles and document the whole process.

I started with a single MOSFET, built CMOS logic gates, figured out how feedback loops can remember bits, then moved on to latches, address decoders, and eventually a working SRAM array capable of reading and writing entire bytes.

The funniest part was how naive and wasteful my implementation is: 47 transistors to store and access a single bit, while production-level SRAM cells do it with just 6. So I dug into that too and ended up turning the whole thing into a heavily illustrated article (thank you Claude), with circuit diagrams at every step. It's heavily inspired by Core Dumped's YouTube channel, which I highly recommend.

Would genuinely appreciate some technical criticism. I'm particularly interested in whether I've oversimplified anything to the point of being wrong: the article


r/compsci • • 1d ago

How Do We Measure Computational Efficiency?

0 Upvotes

Given the same computational problem and verification criteria, what determines the cost of obtaining an exact result?

And which relationships remain invariant when the reference, representation, or scale changes?

In the context of recent developments concerning ETH, these questions invite a comparison of how computational improvements are quantified, including the distinction between asymptotic complexity and measured execution costs.

An experimental algorithmic procedure examines how relationships already present in a structure can be identified, preserved, and reused to obtain verifiable results.

The proposed comparison considers the complete cost of recognizing structure, transforming representations, computing, reconstructing, and verifying the answer.

Can recognizing and reusing existing relationships reduce computational cost, and under which conditions can that reduction be independently demonstrated?

Mathematical observations, alternative measurement criteria, reproducible experiments, and counterexamples are welcome.

Documentation and open discussion:

Computational Efficiency — Open Issue #8

Cost and Recognition

Reproduction Protocol


r/compsci • • 2d ago

Can Quantum Computing Be Fully Understood Through Classical Mathematics?

Thumbnail
reddit.com
0 Upvotes

r/compsci • • 5d ago

Exploring Data Integrity and Fault Tolerance in Erasure-Coded Distributed Storage Systems

1 Upvotes

Hello everyone!

I've been exploring a research direction around distributed storage systems, particularly the challenge of maintaining data integrity and availability when information is distributed across multiple storage nodes.

The research idea I'm investigating is titled:

Verifiable Erasure-Coded Cloud Storage Systems

The problem I'm interested in

Erasure coding allows a system to divide data into fragments and distribute them across multiple storage nodes. This improves storage efficiency and fault tolerance because the original data can be reconstructed even when some fragments become unavailable.

However, distributing data introduces another challenge: how can a storage system efficiently verify that its fragments remain intact and have not been corrupted or improperly modified?

Traditional integrity checks can help detect corruption, but I am interested in exploring verification mechanisms that can operate without requiring the entire original dataset to be reconstructed.

The technical direction

I'm particularly interested in investigating the interaction between:

  • Erasure Coding: Distributing data fragments to improve fault tolerance and storage efficiency.

  • Cryptographic Verification: Establishing confidence in the integrity of stored fragments.

  • Distributed Storage Architecture: Handling node failures, corrupted fragments, and verification across multiple storage nodes.

One challenge I find particularly interesting is balancing verification overhead against storage efficiency, fault tolerance, and system performance.

A question for the community

When combining erasure coding with cryptographic integrity verification, what are the most significant architectural or theoretical challenges that should be considered?

In particular, are there established approaches that allow efficient verification of individual or distributed fragments without reconstructing the entire original dataset?

I'd be interested in relevant research papers, established techniques, and alternative approaches that address this problem.

I'm currently exploring the research literature and refining the problem formulation before moving towards an experimental prototype.

I'd appreciate technically grounded discussion and critical perspectives.

Thanks for reading!


r/compsci • • 6d ago

A Matrix Multiplication Algorithm Rooted In Graph Theory

Thumbnail
leetarxiv.substack.com
0 Upvotes

r/compsci • • 6d ago

Symmetry gives 136 states, the Hankel rank is 51: minimal weighted automaton for 3-colourings of grid strips (review request)

0 Upvotes

For the w × m grid, the number of proper 3-colourings is 1ᵀ Tm−1 1, with T the symmetric transfer matrix on column colourings (1536 states at w = 10). The quotient under S₃ × Z₂ has 136 states. The minimal linear representation (Hankel rank) has dimension 51. Because T is symmetric, the Hankel matrix is a Gram matrix of Krylov vectors, and det H₅₁ ≠ 0 with det H₅₂ = 0 certifies the order exactly.

Minimal orders for w = 1…10: 1, 1, 2, 3, 5, 7, 13, 19, 35, 51. Has anyone seen this sequence, or a structural reason for the gap between the symmetry quotient and the Hankel rank? Details: [CSTheory link]

This opens a broader review request on three costs that are easy to conflate: what stays observable, what a representation must keep, and what a query costs in operations. Two controls separate them. A variable reorder takes the maximum cut rank from 256 to 2 with the same count. Satisfiable Tseitin formulas on expanders need exponential ordered representations yet count in polynomial time by Gaussian elimination. The request lists nine claims with their status and asks where proofs fail, where prior art exists, and whether exact signed decompositions can lower the total cost.

Review request and reproducible lab


r/compsci • • 8d ago

Challenges in calculating ETA at scale

Thumbnail
mehrdadmahabadi.com
4 Upvotes

r/compsci • • 9d ago

OpenAI lowered the matrix multiplication exponent from ~2.371 to 2.25 — here's how the new proof works

Thumbnail
reddit.com
0 Upvotes

r/compsci • • 12d ago

Deriving the Y-combinator

Thumbnail
blog.tinyinterpreters.dev
14 Upvotes

r/compsci • • 15d ago

"Galactus the Devourer", Ben Recht's reaction to The Exponential Time Hypothesis.

Thumbnail
argmin.net
184 Upvotes

r/compsci • • 17d ago

Deterministic factoring in time N^o(1)

Thumbnail
reddit.com
7 Upvotes

r/compsci • • 20d ago

The Exponential Time Hypothesis is false

Thumbnail
github.com
663 Upvotes

r/compsci • • 23d ago

What if brain surgery affected your ability to code?

48 Upvotes

Imagine we need brain surgery to remove a tumor. The surgery goes well, but afterward, you struggle to write or understand code. Scary, right?

We know that neurosurgeons try to preserve important abilities like speaking and moving during brain surgery. But what about programming?

A new study in Human Brain Mapping explores exactly this!

The researchers developed a new protocol during awake brain surgery to help identify and preserve brain areas involved in programming.

The idea is simple: if coding is an important part of someone's life, shouldn't we try to preserve that ability too?

Here's the paper: https://doi.org/10.1002/hbm.70634


r/compsci • • 24d ago

I made a game to teach digital logic: build up from NAND gates to a working CPU

153 Upvotes

I made a game to teach computer architecture and digital logic: play.simten.dev

You start with basic logic gates and build up to a working CPU. It's built on Simten, a TypeScript-based HDL, so you write the circuits as code and they show up live on a canvas next to the editor. For sequential circuits you can scrub the clock backwards and forwards to watch the state change cycle by cycle. You can also drill down into abstracted components (like the half adder shows). Because of the layout it only works on desktop browsers for now.

It's open source, any feedback or contributions are welcome!


r/compsci • • 27d ago

I built a canvas simulator for automata theory: DFA/NFA/PDA/Turing machines, regex to NFA conversion, and real-time team collaboration

Thumbnail
gallery
22 Upvotes

Spent the last while building this: a browser based canvas where you can draw and run finite automata, pushdown automata, Turing machines, and Mealy/Moore machines, all with animated step-by-step execution.

A few things it does that I'm proud of:

- Converts a regex into an NFA (Thompson's construction), then NFA into a minimized DFA (subset construction), and can extract a regex back out of an automaton (FA to GNFA to regex)

- Local first: works fully offline with localStorage, no account needed

- Optional accounts unlock "Teams": real time collaborative canvases with live cursors and presence, so you can whiteboard an automaton with someone else the same way you'd use Figma

- There's a learning section with guided lessons, each paired with a live, editable simulator embed instead of static diagrams

It's free to use: theoryofcomputationsimulator.com

Would love feedback, especially from anyone who's TA'd or taken a theory of computation course and can poke holes in the UX.


r/compsci • • 27d ago

No scripts: a virtual fly driven by its real brain wiring diagram (70k simulated neurons), live 24/7

Post image
275 Upvotes

Body:

> Not an RL agent and not a behaviour tree — the "policy" is a spiking simulation of a real fly connectome, and the body

> is a MuJoCo fly whose legs are moved by an imitation-learned network. It sees, smells wind-borne odor, gets scared by

> spiders, grooms, lands, eats. Everything that isn't the brain is labelled on screen. Live: twitch.tv/dodo_gun


r/compsci • • 27d ago

what is context switching?

2 Upvotes

I know this has been discussed before, but it's extremely confusing for me because of how many variations there are in definitions. Here are some observations:

  1. Most people would agree that process-switches and system calls both involve context switching, however I think the underlying "state saving" is different between these two events. In a system call, there is an entry phase where the kernel saves register state to the kernel stack (and not every system call leads to a process or thread switch). In a process-switch, the PCB gets updated so that the process can later be resumed. Is this accurate?

  2. On Linux, both processes and threads are schedule-able (they're both "tasks"). As best as I can understand, there's a function called context_switch() in the Linux kernel that gets called during scheduling. However, it seems context switching is used in a broader sense. In other words "context switching" doesn't mean exactly that we're calling the function "context_switch()".

  3. There is at least one textbook that considers functions as having their own context (Doeppner's Operating Systems in Depth). This is a little confusing because I can't find anyone else who considers a function call a change in context.

The question is: does anyone have a technical definition of context switching that captures what most people mean when they say "context switch"?

I've also been reading about the xv6 since it's a smaller educational operating system. If somebody has experience/knowledge of the xv6 internals, I would appreciate any input. Thank you