I've had this idea lately about a way to distinguish P and NP and I'm curious if this had been explored before. P and NP both have a "solution space" of answers to those problems. Would it be interesting to try to distinguish P and NP by finding an NP complete problem with a set of solutions that is not recursively enumerable?

I was reading about sparse least-squares solvers and came across this paper at http://arxiv.org/abs/2608.02588v1. The abstract claims a lower bound: even for randomized poly-time algorithms, you can’t beat a linear dependence on the restricted condition number $κ_{s+k}$ when trading off sparsity and error tolerance. That feels like it has teeth, but I'm not sure how it maps to practice.

What I'm confused about

In the real world, practitioners often heuristic-sparsify models (e.g., feature selection in ML, compressed sensing) or use iterative hard thresholding. Does this lower bound mean those methods are *fundamentally* limited, or does the result rely on assumptions that don't hold in typical use cases? The paper conditions on a variant of the Small-Set Expansion Hypothesis, which is a complexity-theoretic assumption but not something engineers usually worry about.

Tradeoffs in the proof

The authors mention using an automated Gemini-based agent system to first construct the proof. That part fascinates me, but my CS theory chops are too weak to judge whether the reduction itself (from a graph hypothesis to a linear algebra problem) preserves practical relevance. The result holds even on rational instances with full-rank matrices, so the hardness doesn't hinge on numerical pathologies. Yet I haven't seen this cited in any applied optimization forums yet.

Has anyone implemented sparse regression workflows where the condition number $κ$ scales steeply with problem size? If so, does this paper suggest a fundamental ceiling on how well approximate methods can perform, or is there wiggle room in relaxing the hardness hypothesis? I’m curious whether this is more of a theoretical boundary condition or something that bites practitioners in the wild.

Also, the proof relied on automation. Are there follow-up efforts to formalize or verify the result independently (e.g., in Lean or Isar)? That feels like a separate discussion.

I am self studying Operating Systems. I have understood semaphores and monitors up until this point (I think). The textbook (OS Concepts by Silberschatz) implements signal-and-wait Monitors with one condition variable x in the following way:

// semaphores
mutex = 1
next = 0
x_sem = 0

//counters
x_count = 0
next_count = 0

// Monitor function F()
wait(mutex)
F()
if (next_count > 0)
  signal(next)
else
  signal(mutex)


//x.wait()
x_count++
if(next_count>0)
  signal(next)
else
  signal(mutex)
wait(x_sem)
x_count--


//x.signal()
if(x_count>0){
  next_count++
  signal(x_sem)
  wait(next)
  next_count--
}

Suppose I have 3 processes P1, P2 and P3

P1 signals P2 to awaken in its lifetime and P2 signals P3 to awaken in its lifetime

initially, P1 will be waiting on the wait(next). then P2 will also be waiting on wait(next).

When P3 is either done or is about to wait, it will signal(next). However, there is no mechanism (like maybe a stack) to ensure that P2 is the process that awakens and not P1. Does this not violate the conditions for Hoare-style (signal-and-wait) Monitors. Does the book simply omit this because it is a trivial addition or have I missed some essential concept ?

If LLMs are all trained off stolen data and open source repositories, this means they're essentially laundering a large amount of open source code without the proper dues paid to the licensing requirements, such as CC-4.0 for example which would explicitly require credit from original sources.

This would in turn make any vibe-coded app illegal based off licensing requirements, if one were to find a 1:1 copy of their code within an open-source vibecoded app, no?

I know that's a kind of hard legal requirement to reach, since there's only a finite way of doing things within a language's framework and therefore blindly accusing everyone who ever does the same function as you as a vibecoder would be painful to say the least.

But there's an increasing amount of people who believe the "spirit" of FOSS/FLOSS is preserved when vibecoding if they make their code source-available as well, completely disregarding the legal frameworks around GPL/LGPL/CC-4.0 etc.

Posting this here but idk if I would be best served in a legal subreddit.

Edit: To clarify, I'm not entirely against the use of AI/LLMs, I'm just curious about what the line is legally speaking when people say "I made this app!" and it's 4 different FOSS projects stapled together without credit.

I’ve been seeing a lot of news about how bad it is and stuff. I see it everywhere, on job applications, in classes, on social media etc. Could it really pull an Ultron? Is it just a fad?

Are the programmes currently being reverse-engineered by AI actually being reverse-engineered in the traditional sense? In other words, is the source code actually being uncovered? Or are the programmes simply being copied on the basis of their functions, behaviour and so on?

I’ve noticed that whenever people talk about AI taking over jobs, the discussion almost always revolves around software engineers, computer science graduates, and IT professionals.
But what about all the other industries? Many jobs involve repetitive tasks or work that AI could potentially automate, yet they don’t seem to receive nearly as much attention as tech careers do.
Why is the internet so focused on discouraging people from studying computer science or pursuing careers in tech, while seemingly ignoring the potential impact of AI on so many other professions?
Is there a particular reason tech jobs get so much attention, or is it simply because people in the tech industry are more aware of AI’s capabilities and are more vocal about it?
I’d genuinely like to understand why this discussion seems so heavily concentrated on technology careers.

A lot of very recent projects making headlines are using LLMs to code the majority. Counting the learning, prompt and output, how much do these independent projects actually end up spending? I would prefer at least one direct example like the one below, but direct numbers from experience of any software would be awesome. Below is an example of a headline, but more examples would average things out.

https://www.techspot.com/news/114042-you-can-now-play-original-halo-browser-128.html

Would be nice to include certain details like: what length of time did the project take from start to finish, what is the cost of the input versus the output tokens (I'm not familiar with the terms)? Is there iterative steps, mistakes to redo?

For a project, are they personal licenses, paying by the token? What model(s)? Is it a single user paying out of pocket or is that user/users just using a license provided by their work?

What are the best resources to learn the important AI Engineering skills like LLMs, RAG, vector databases, agents, LangChain/LangGraph, and deployment?
For people who learned these, what courses or resources did you find most useful?

Is it just me or computer science is hard to grasp. I just entered my 4th week in a top private university and this university is very known for its computer science and IT.

I got 3 math classes - statistics, discrete, linear algebra - and holy it’s hard asf (both discrete and linear). Not to mention the programming class? Wtf is c man like I can code and I usually run in python, html, css, js but c is entirely a different language, array and pointers omds. I dont think the average joe would handle this😭

Give me tips pls

Hi, this is coming from a Junior developer with basic system design skills. To the senior engineers or architects out there, how good are the latest frontier models like Opus 5.5 at designing large production systems? Where does it excel (if any)? And where does it fail? Can you give real-world examples or personal experiences you've come across when using these models? Opus 5.5 blew me away when it came out, so I'm wondering if it improved in the system design department as well.

Can you get very far with writing in simple English enough that people can understand you? Thank you.

The Scariest AI Breakthrough

This video is around 3 minutes and is more or less a very dry comedy sketch, but it sums up an idea I've seen around the internet in the last 3 or 4 days. It's a worth a watch to get the full context.

But the thrust is that the ability of generative coding agents to reverse engineer and "fuse" together two separate games from different game engines and have them be in an at least playable state (some of them working really well apparently) is a set up for a technological apocalypse. Someone with a little bit of knowhow can now vibe code things in a couple days that are so complex that it would have taken years to do before, if it was even possible at all. A bit like giving people a legitimate ability to building working nuclear weapons they can 3D print at home.

I have been skeptical (an understatement) of the sales pitch of Anthropic and OpenAI and their ilk at this point. But I can't deny this is a compelling idea. So far, their "AI that's too dangerous it's broken out of containment" sales pitch has really not done good things for their AI's credibility; it's disingenuous at best. "We told it to do A & B, but we never told it to do C, explicitly. It may have just gotten that purgative from the first two instructions".

But I can now see a real-world example of something that should almost not be possible, in my understanding, to being possible. But I'm also keenly aware that what's going on with these game mashups isn't indicative necessarily of say, being able to disrupt other technological infrastructure like banks. 

So, what is the real story here? Are we headed towards a cliff here or is this something else? Is it somewhere in between?

Hello,

I'm writing a sci-fi thriller mystery about AI and stumbled across this video by Jaden Williams (who I believe has a degree in computer science).

Jaden Williams Video

He may have made it a little too doomsday like for comedy purposes obviously but how accurate is he being with this? If it's very much, does the concept have a name and do you know of any sources (scholarly journals, books, news articles) that discuss it?

I'm asking because if it's accurate, it might be something I'd like to include in my story.

If it's not, then there's not really a point of further discussion I guess lol.

All help is greatly appreciated, thank you!

How do you guys study automata man, it's my mid sem this Monday, and even 20 marks is feeling like hell.

Idk what that professor would ask, dfa, state diagrams!!

Help me out please 😭

Hi there! My name is Mike and I teach computer science. I was wondering whether students should be allowed to program and problem solve with AI assistance or not. Do you think this will change much over the next few years? If you have any thoughts or preferences based on your personal experience, I would be very excited to hear! Thank you!

How to find eigenvectors of non-symmetric matrix?

I know well the trade off between domain languages / efficiency compared with c / assembler

CPU / memory are fast enough for good enough performance but with memory supply issues I wondered if direction were going to be able develop better domain languages to break trade off.

modern compilation - reflection - macros - templates

languages like c should only be written by experts and or machines imo way too risky for domain users.

Eg in audio domain I want to write code fast enough for realtime have it expanded to low level code - using linked list/stack/heap/hash/midi etc

Instrument a as piano :
a.octave = + 2
a.root = g
a.feel = shuffle
a.scale = enigma
a.play(100)

I don’t want to manage memory / lifetime or use library
Ie I want the compiler to do the translation?

Is this reasonable or am I dreaming ? Do you think we need stronger reflection ie I probably need to work with ast at the moment.

I know most standard math libraries have log1p and expm1 functions that calculate log(1+x) and exp(x)-1 more accurately than those expressions themselves do when x is close to zero, because they avoid the bug increase in unit-in-the-last-place size that occurs when a double smaller than 0.5 is added to or subtracted from 1.0. Why isn't there a function that does that for 1-cos(x), given that that expression has the same problem? Is it not used widely enough where x is given as an angle? (I guess it might not be used as a machine-learning distance metric, since there the cosine is calculated directly from the vector coordinates.)

Books in math, computer science, and philosophy are welcome. What order would I read books on the first, second and third wave of cybernetics?

a joint venture between Tesla & SpaceX

I have no expertise in the field, but from far as I know, neither company has experience in semiconductor manufacturing, nor cutting-edge electronic hardware in general (in terms of design or manufacturing)

so what's the prospect here, how do they plan to overtake & out-compete established firms in the field (other than Musk's wealth & his ability to attract disproportionate amount of investment from capital markets), say for instance, Samsung or TSMC or Intel

I can't find any detailed plan about their core strategy, or any 'genius' idea that would propel them ahead of status quo, and the website is a bit of a joke in my opinion

Would like to consult your opinion on this new venture of his — those who are familiar with the field — is it viable, what's the play here, etc.

Thanks in advance

is it possible to pool processing power, like my android has dimensity 6400 , and my laptop has i31115g4, when using the laptop i mostly use phone as hotspot only so the processor is idle there, is there a way that i can put lighter processing stuff to the phone's cpu and other work on my pc to unload the unecessary small tasks.

It seems to me (an outsider): AI has always been a thing of interest, very useful for sure, lots of potential, but has anything that significant really happened since circa 2022? to solicit such attention & resources, from everyone, everything, everywhere

I never really got what the hype since circa 2022 was all about — yes 'AI' is great, and could be very capable, but that was the case since the 1980s (from first development by Hinton et al., to DeepBlue, to DeepMind, Siri, etc.) ; it has progressed, sure, and will progress, but why all the sudden all the fuss just now? and the exponential hike in investment just now and not on a scale as before?

Another thing: it seems to me that 'AI', as a term, is rather quite broad — almost in the same vein as 'intelligence', or 'life', or 'God'. So when people say AI will change everything, I don't really know what that means. People behind these narratives almost never seem to be concerned with the reality of technical progress — technicality/timeline of what's possible when, but merely extrapolate based on a single data point.

To me: '[AI] will be able to cure cancer' almost sounds like '[Genius intelligence] or [God] will be able to cure cancer' — sure, maybe, eventually; but when, and how?

again, I am not at all familiar with the technical side of things (being a chemist who can't code, who occasionally use it from time to time, mostly chatbot and specialised model for pattern-analysis), I am not trying to be skeptical, or pessimistic, but just from empirical observation — I feel like I could've done most if not all the things before 2022, without chatbots etc. (professionally or everyday); it really doesn't seem like a revolution since 2022, more like a steady progression (promising of course, but so are so many other things), especially considering the sheer scale of investment put into it

So, what's the verdict? I guess if we invest enough and concentrate enough on one thing eventually something, if anything) will happen, it will be here; but are we really on the verge of singularity literally 2 weeks from now, or will it eventually die down as almost everything before it did?

Assume you can go back in time to the early days of networking (pre-TCP/IP, early ARPANET) with today's knowledge of cryptography, routing, and state-level censorship tools (DPI, IP/SNI blocking, middleboxes). How would you design the foundational network architecture so that any state or ISP choosing to route traffic must accept either 100% uncensored, unmonitored connectivity or a complete blackout, with no technical middle ground?

Specifically (but not limited to the following)

• Protocol-Level Constraints: How do you structure the transport/routing layer so that inspecting, filtering, or modifying a single packet breaks the connection for the entire link or network participant?
• Metadata & Routing: How do you eliminate or obscure traffic metadata (IP headers, SNI, packet sizes, timing signatures) at the lowest layer so middleboxes cannot perform selective deep packet inspection or domain-level blocking?
• Bootstrapping & Topology: How do you solve the entry-point discovery problem without relying on centralized, blockable infrastructure like traditional root DNS or static IP allocation?

... Is a true "all-or-nothing" censorship-resistant network protocol theoretically possible without state actors physically cutting transoceanic cables or severing border connections?

pick one:

a) The token's signature becomes invalid once it is revoked, so verifiers cannot distinguish revocation from tampering b) Revocation requires the client to cooperate by discarding its copy c) Verifiers must consult shared state, which is what the format avoided d) The issuer cannot identify which token to revoke without storing them all

b, or am i misreading the question

went b. a self-contained token is verified offline, so the only way i can see to kill it early is the client agreeing to throw it away. d also felt close though