Amplifying the Computational No-Coincidence Conjecture 2025-03-07T21:29:54.933Z

Sleeping Beauty: an Accuracy-based Approach 2025-02-10T15:40:29.619Z

Comment by glauberdebona on Amplifying the Computational No-Coincidence Conjecture · 2025-03-11T01:53:08.761Z · LW · GW

Correcting myself: "doubly" just added above.

Comment by glauberdebona on Amplifying the Computational No-Coincidence Conjecture · 2025-03-11T01:35:15.014Z · LW · GW

For the time-complexity of the verifier to grow only linearly with $O\left(\log 1/\epsilon \right)$, we need also to assume the complexity of the reduction $f_m$ is $O\left(|C{|}^{\gamma }\right)$ for a fixed $\gamma$, regardless of $m$, which I admit is quite optimistic. If the time-complexity of the reduction $f_m$ is doubly exponential in $m$, the (upper bound of the) time-complexity of the verifier will be exponential in $1/\epsilon$, even with the stronger version of Reduction-Regularity. 

Comment by glauberdebona on Amplifying the Computational No-Coincidence Conjecture · 2025-03-11T00:50:55.021Z · LW · GW

By "unconditionally", do you mean without an additional assumption, such as Reduction-Regularity?

I actually have a result in the other direction (an older version of this post). That is, with a slightly stronger assumption, we could derive a better upper bound (on $1/\epsilon$) for the time-complexity of the verifier.  The stronger assumption is just a stronger version of Reduction-Regularity, requiring $Prob\left(f\right(C)\in \overline{V_0}|f(C)\in \overline{P})\ge \delta$ -- that is, $\overline{V_0}$ replaces $\overline{L}$ in the inequality. It could still lead to an exponential bound in $1/\epsilon$ if the complexity of the reduction $f_m$ increases exponentially with $m$. In the version presented in this post, the exponential bound relies on the complexity of $f_m$ being $O\left(|C{|}^{\gamma }\right)$ for a fixed $\gamma$, regardless of $m$, which is admittedly optimistic. If we assume this with the stronger version of Reduction-Regularity, then I think the upper bound for the time-complexity of the verifier would increase only linearly with $m=O\left(\log 1/\epsilon \right)$, which is a huge improvement (I can add something in the appendix about this if you are interested in the details). In the end, I opted for presenting the weakest assumption here, even if corresponding to a worse complexity bound.

Comment by glauberdebona on A computational no-coincidence principle · 2025-03-08T11:24:32.388Z · LW · GW

Your comment seems to imply that the conjecture's "99%" is about circuits $C$ for which $P\left(C\right)$ is false. Otherwise, it would be impossible for a $V$ to miss 100% of random reversible circuits without missing the circuits $C$ for which $P\left(C\right)$ is true. In the conjecture, should "random reversible circuits $C$" be read as "random reversible circuits $C$ for which $P\left(C\right)$ is false"? It does not change much indeed, but I might have to correct my presentation of the conjecture here.

Comment by glauberdebona on A computational no-coincidence principle · 2025-03-07T21:34:31.640Z · LW · GW

I think I have an idea to make that 99% closer to 1. But its development became too big for a comment here, so I made a post about it.

Comment by glauberdebona on Sleeping Beauty: an Accuracy-based Approach · 2025-02-11T14:09:46.182Z · LW · GW

Thanks for the feedback! The summary here and the abstract in the draft paper have been updated; I hope it is clearer now.

Comment by glauberdebona on Open Thread Winter 2024/2025 · 2025-02-05T16:55:15.537Z · LW · GW

Hi everyone,

I’m Glauber De Bona, a computer scientist and engineer. I left an assistant professor position to focus on independent research related to AGI and AI alignment (topics that led me to this forum). My current interests include self-location beliefs, particularly the Sleeping Beauty problem.

I’m also interested in philosophy, especially formal reasoning -- logic, Bayesianism, and decision theory. Outside of research, I’m an amateur chess player.