LESSWRONG
LW

glauberdebona — LessWrong

Correcting myself: "doubly" just added above.

Replying toAmplifying the Computational No-Coincidence Conjecture

Amplifying the Computational No-Coincidence Conjecture

For the time-complexity of the verifier to grow only linearly with , we need also to assume the complexity of the reduction $f_{m}$ is $O (| C |^{γ})$ for a fixed $γ$ , 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 / ε$ , even with the stronger version of Reduction-Regularity.

Replying toAmplifying the Computational No-Coincidence Conjecture

glauberdebona1y

Amplifying the Computational No-Coincidence Conjecture

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 / ε$ ) for the time-complexity of the verifier. The stronger assumption is just a stronger version of Reduction-Regularity, requiring $P r o b (f (C) \in_{0} | f (C) \in ¯ ¯¯ ¯ P) \geq δ$ -- that is, $_{0}$ replaces $¯ ¯¯ ¯ L$ in the inequality. It could still lead to an exponential bound in $1 / ε$ 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 (| C |^{γ})$ for a fixed $γ$ , regardless of $m$ , which is admittedly optimistic. If we assume this with the stronger version of Reduction-Regularity, then... (read more)

Replying toA computational no-coincidence principle

glauberdebona1y

A computational no-coincidence principle

Your comment seems to imply that the conjecture's "99%" is about circuits for which $P (C)$ 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 (C)$ is true. In the conjecture, should "random reversible circuits $C$ " be read as "random reversible circuits $C$ for which $P (C)$ is false"? It does not change much indeed, but I might have to correct my presentation of the conjecture here.

Replying toA computational no-coincidence principle

glauberdebona1y

A computational no-coincidence principle

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.

Amplifying the Computational No-Coincidence Conjecture

glauberdebona

Introduction

Recently, the Computational No-Coincidende Conjecture^[1] was proposed, presented as an assumption that might be needed to develop methods to explain neural nets in the current approach from the Alignment Research Center. In this post, I will prove that some plausible extra assumption can be used to amplify the conjecture, showing it implies an arbitrarily stronger version of itself.

In a slightly weakened version, the conjecture reads:
(weak) Computational no-coincidence conjecture: For a reversible circuit $C : {0, 1}^{3 n} \to {0, 1}^{3 n}$ , let $P (C)$ be the property that there is no input $x$ to $C$ that ends in $n$ zeros, such that $C (x)$ also ends in $n$ zeros. There exists a polynomial-time verification algorithm $V$ that receives as input:

A reversible circuit $C : {0, 1}^{3 n} \to {0, 1}^{3 n}$
An advice string $π$

such that:

For all $C$ such that $P (C)$ is true, there exists $π$ with length polynomial in the size of $C$ , such that $V (C, π) = 1$ .
For 99%

... (read 1916 more words →)

Replying toSleeping Beauty: an Accuracy-based Approach

glauberdebona1y

Sleeping Beauty: an Accuracy-based Approach

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

Sleeping Beauty: an Accuracy-based Approach

glauberdebona

This post does not propose a solution to the Sleeping Beauty problem, but presents arguments based on accuracy for thirders, halfers and double-halfers. A more detailed draft paper can be found here.

Summary

Accuracy-based arguments claim that one should plan to adopt posterior credences that maximize the expected (according to prior credences) accuracy. Applying this approach to the Sleeping Beauty problem, the solution depends on how we aggregate the accuracy of the credences held in the two indistinguishable awakenings when the coin lands Tails. Kierland and Monton (2005) have shown that, employing the Brier score, averaging accuracy yields halving ( $p = 1 / 2$ ), and summing leads to thirding ( $p = 1 / 3$ ). We generalize that result for any strictly proper... (read 1827 more words →)

Replying toOpen Thread Winter 2024/2025

glauberdebona1y

Open Thread Winter 2024/2025

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.