Recent Questions - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2023-12-07T01:44:09Z https://cstheory.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/53621 0 How to properly learn when there is random classification noise? meeeeee https://cstheory.stackexchange.com/users/70055 2023-12-06T03:36:00Z 2023-12-06T03:36:00Z <p>The following problem is motivated by the one <a href="https://www.cs.ox.ac.uk/people/varun.kanade/teaching/AML-HT2017/sheets/sheet5.pdf" rel="nofollow noreferrer">here</a> from more than half a decade ago:</p> <blockquote> <p>Let <span class="math-container">$C$</span> be a concept class that is efficiently proper PAC-learnable, i.e. there exists a learning algorithm that outputs <span class="math-container">$h \in C$</span>, such that <span class="math-container">$\mathrm{err}(h) \leq \epsilon$</span>, in addition to the usual PAC-guarantees. Suppose that this same class <span class="math-container">$C$</span> is PAC-learnable in the presence of random classification noise, but that the learning algorithm for <span class="math-container">$C$</span> in this setting. Show that <span class="math-container">$C$</span> is also proper PAC-learnable in the presence of random classification noise.</p> </blockquote> <p>In the standard setting without noise, the existence of an efficient proper PAC-learning algorithm for the class <span class="math-container">$C$</span> implies that we can find a hypothesis <span class="math-container">$h \in C$</span> with an error rate of at most <span class="math-container">$\epsilon$</span>. However, when introducing random classification noise, the challenge is that the labels of the instances may be flipped with some probability, say <span class="math-container">$\eta$</span>, which complicates the learning process.</p> <p>My initial approach was to adapt the standard learning algorithm for <span class="math-container">$C$</span> to account for the noise. I considered techniques such as noise-tolerant variants of the algorithm or methods to estimate and correct the flipped labels. However, I am uncertain about how to guarantee that the modified algorithm still outputs a hypothesis from the class <span class="math-container">$C$</span> (thus ensuring proper learning) while maintaining the error rate within the desired bounds. I'd appreciate any help.</p> https://cstheory.stackexchange.com/q/53619 3 A variation of propositional pigeonhole principle Soha https://cstheory.stackexchange.com/users/68233 2023-12-05T00:13:48Z 2023-12-06T10:16:44Z <p>Let <span class="math-container">$n$</span> be the number of pigeons, and <span class="math-container">$x_{i,j}$</span> denote the Boolean variable indicating that pigeon #<span class="math-container">$i$</span> is mapped to hole #<span class="math-container">$j$</span>. Then the propositional pigeonhole principle (PHP) is the conjunction of following clauses:</p> <ol> <li><span class="math-container">$x_{i1}\lor x_{i2}\lor\cdots\lor x_{i,n-1}$</span>, <span class="math-container">$\forall 1\le i\le n$</span> (a pigeon must be mapped to at least one hole)</li> <li><span class="math-container">$\neg x_{ik}\lor\neg x_{jk}$</span>, <span class="math-container">$\forall 1\le i&lt;j\le n,1\le k\le n-1$</span> (two pigeons <span class="math-container">$i,j$</span> cannot be mapped to the same hole <span class="math-container">$k$</span>)</li> </ol> <p>We know that the PHP formula is unsatisfiable. The reason why we can use &quot;a pigeon must be mapped to at least one hole&quot; instead of &quot;a pigeon must be mapped to <em>exactly</em> one hole&quot; is that, if a pigeon occupies multiple holes, then the remaining pigeons are even &quot;less&quot; likely to be accommodated. Now we consider replacing each <span class="math-container">$\neg x_{i1}\lor\neg x_{j1}$</span> with <span class="math-container">$\neg x_{i1}\lor\bigvee\limits_{t=2}^{n-1}x_{it}\lor\neg x_{j1}\lor\bigvee\limits_{u=2}^{n-1}x_{ju}$</span> (<em>Note that the loosened constraints only apply to hole #1; otherwise the formulas would be satisfiable</em>). After this, the formula is still unsatisfiable, since albeit the conditions are loosen, those <span class="math-container">$x_{it}$</span>'s and <span class="math-container">$x_{ju}$</span>'s can't be really set to true, because otherwise there will be no enough holes for the remaining pigeons. More intuitively, the replacement allows us to map pigeons #<span class="math-container">$i,j$</span> to the same hole #<span class="math-container">$k$</span> at the expense of mapping at least one of #<span class="math-container">$i,j$</span> simultaneously to another hole. Since a pigeon occupies at least two holes, the number of holes is still not enough so the contradiction still persists.</p> <p>We know that the original PHP has a polynomial-size Frege proof saying that &quot;from condition #1 we can infer that at least <span class="math-container">$n$</span> variables are satisfied, but from #2 we infer that at most <span class="math-container">$n-1$</span> variables are satisfied, which leads to contradiction&quot;. My question is, in this case, can we still construct a polynomial-size Frege proof for the modified formula?</p> <p><em>update</em>: I found that the constraints can be furthur loosened while preserving unsatisfiability. In this case we replace each <span class="math-container">$\neg x_{ik}\lor\neg x_{jk}$</span> with <span class="math-container">$\neg x_{ik}\lor\bigvee\limits_{t=k+1}^{n-1}x_{it}\lor\neg x_{jk}\lor\bigvee\limits_{u=k+1}^{n-1}x_{ju}$</span> (this time constraints for all holes for loosened, unlike in the first case where only constraints for hole #1 is loosened). This makes the formulas even harder to prove, since now the problem will not degenerate to vanilla PHP when we set some variables to true. The intuitive reason for the unsatisfiability is similar: if we let two pigeons occupy the same hole, at least one of them must also occupy another hole whose index is greater than the current one, so that the the number of holes is still not sufficient (this ordering constraint rules out the counterexample given by Joshua). Also, I used Python and PySAT to verify the unsatisfiability of these formulas and it turned out that they're still unsatisfiable up to <span class="math-container">$n=10$</span>.</p> https://cstheory.stackexchange.com/q/53618 0 Impossibility of uniform generation in random world Pur2all https://cstheory.stackexchange.com/users/60745 2023-12-05T00:05:32Z 2023-12-05T00:05:32Z <p><strong>I specify that this is a <a href="https://crypto.stackexchange.com/questions/108929/impossibility-of-uniform-generation-in-random-world">cross-post</a> from crypto.stackexchange</strong></p> <p>I was reading <a href="https://dl.acm.org/doi/10.1145/73007.73012" rel="nofollow noreferrer">Limits on the provable consequences of one way permutations</a> by Impagliazzo and Rudich when I got stuck on a sentence.</p> <p>First of all, they define a polynomial relation that is any relation <span class="math-container">$R$</span> verifiable in polynomial time in <span class="math-container">$||x|| + ||y||$</span>, i.e., <span class="math-container">$xRy$</span> iff we can decide in poly time if <span class="math-container">$y$</span> is a valid assignment of values for boolean formula <span class="math-container">$x$</span>.<br /> After this, they define Uniform Generation, that is a problem in which given <span class="math-container">$x$</span>, one have to pick a <span class="math-container">$y$</span> uniformly at random such that <span class="math-container">$xRy$</span>.<br /> A PPT algorithm <span class="math-container">$\mathcal{A}$</span> is said to be a generator for <span class="math-container">$R$</span> if given <span class="math-container">$x$</span> it will output a uniformly chosen <span class="math-container">$y$</span> with at least <span class="math-container">$1/2$</span> of chances.<br /> Then they cite a theorem (3.1) that states &quot;For any polynomial-time relation, there exists a PPT algorithm <span class="math-container">$\mathcal{A}$</span> equipped with a <span class="math-container">$\Sigma_2^P$</span> oracle that uniformly generates it.&quot;</p> <p>In page 6, at the start of section 4.2 they say that Uniform Generation is impossible in a random world, i.e. a world with a Random Oracle, and they specify that it is impossible to uniform generate an inverse of a random function.<br /> More in detail, they first state the theorem 4.1 which states that a random function is &quot;strongly one-way&quot;, which means that it is information-theoretically one-way, i.e., every PPT algorithm has expectation of inverting that is no more than <span class="math-container">$poly(n)/2^n$</span> for an input of length <span class="math-container">$n$</span>.<br /> Immediately after they say &quot;Theorem 4.1 implies that uniform generation is impossible in a random world; it is impossible to uniformly generate an inverse to the function associated with the oracle.&quot;</p> <p>My question is why it is impossible?<br /> I mean, checking if a given <span class="math-container">$y$</span> is an image of a one way function <span class="math-container">$f$</span> evaluated on <span class="math-container">$x$</span> is clearly a polynomial time relation. Since the algorithm to evaluate <span class="math-container">$f$</span> is a polynomial algorithm, given <span class="math-container">$x$</span> and <span class="math-container">$y$</span> it is simple to check if <span class="math-container">$xRy$</span> (in this case maybe is better to write <span class="math-container">$yRx$</span>) by computing <span class="math-container">$f(x)$</span> and check if it is equal to <span class="math-container">$y$</span>.<br /> Why I can't use the theorem 3.1 and say that there exists the algorithm that uniformly generate an inverse?</p> https://cstheory.stackexchange.com/q/53617 0 word2vec: vectors or projective vectors? Tegiri Nenashi https://cstheory.stackexchange.com/users/3213 2023-12-04T22:31:21Z 2023-12-05T17:07:49Z <p>In <a href="https://arxiv.org/pdf/1301.3781.pdf" rel="nofollow noreferrer">&quot;Efficient Estimation of Word Representations in Vector Space&quot;</a> Mikolov et.al argue that any mapping of words into vectors should satisfy approximate constraints, such as</p> <p><span class="math-container">$vector(''Paris'') - vector(''France'') + vector(''Poland'') \approx vector(''Warsaw'')$</span></p> <p>Then, on page 5 they choose the Cosine distance to measure the vector proximity. Unfortunately, cosine distance is not a metric. It hints however that perhaps the problem setup has to be transferred into Euclidean Projective space. Unfortunately, there is <a href="https://math.stackexchange.com/questions/462834/is-a-projective-space-a-vector-space-if-not-what-of-a-basis">no identity element</a> in projective space. Why the authors didn't use a conventional norm, such as <span class="math-container">$l^2$</span>?</p> https://cstheory.stackexchange.com/q/53616 0 Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity Jika https://cstheory.stackexchange.com/users/23055 2023-12-04T04:56:57Z 2023-12-04T04:56:57Z <p>I have <span class="math-container">$m$</span> items and <span class="math-container">$n$</span> bins where each item <span class="math-container">$i$</span> and bin <span class="math-container">$j$</span> has a value <span class="math-container">$v_{i,j}$</span>. Each bin <span class="math-container">$j$</span> has a value <span class="math-container">$V_j$</span>. I want to pack the items into the bins such that</p> <p>(1) I minimize the ratio of the values of packed items to the number of packed items while using all bins;</p> <p>(2) an item can be packed into only one bin; and</p> <p>(3) The values of the item packed into bin <span class="math-container">$j$</span> is at least <span class="math-container">$V_j$</span>.</p> <p>If <span class="math-container">$S_j$</span> are the items packed in bin <span class="math-container">$j$</span>, then I want to maximize <span class="math-container">$\sum_j\sum_{i\in S_j}v_{i,j}/\sum_j|S_j|$</span> such that <span class="math-container">$\sum_{i\in S_j}v_{i,j}\ge V_j$</span>.</p> <p>I have been looking for this problem on the internet and I found that it is very similar to the GAP problem or the Min-GAP problem (<a href="https://epubs.siam.org/doi/abs/10.1137/S0097539700382820?journalCode=smjcat" rel="nofollow noreferrer">https://epubs.siam.org/doi/abs/10.1137/S0097539700382820?journalCode=smjcat</a> or <a href="http://www.or.deis.unibo.it/kp/Chapter7.pdf" rel="nofollow noreferrer">http://www.or.deis.unibo.it/kp/Chapter7.pdf</a>) but I am not sure if it is equivalent to one of them. In GAP, we are maximizing the profit while guaranteeing the capacity of each bin. In Min-GAP, we are minimizing the cost while also guaranteeing the capacity of each bin.</p> <p>In my problem, I have no limit on the capacity of each bin. Even if I want only to minimize <span class="math-container">$\sum_{j}|S_j|$</span> or maximize <span class="math-container">$\sum_j\sum_{i\in S_j}v_{i,j}$</span>, the problem seems different than GAP or Min-GAP.</p> <p>If you see any obvious reduction, can you describe how to reduce my problem (or the linear variants I described above) to GAP or Min-GAP so that I can efficiently solve my problem.</p> https://cstheory.stackexchange.com/q/53614 3 Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard? rus9384 https://cstheory.stackexchange.com/users/45276 2023-12-03T10:18:50Z 2023-12-06T02:09:52Z <p>It's suspected that probabilistic complexity classes such as <span class="math-container">$\mathsf{RP}$</span> or <span class="math-container">$\mathsf{BPP}$</span> don't have complete problems. Of course, their promise counterparts have complete problems, but I am not asking about promise problems. So, I have relaxed the restriction of <em>completeness</em>.</p> https://cstheory.stackexchange.com/q/53613 -4 would statistical randomness disprove P=NP ChadTheVlad https://cstheory.stackexchange.com/users/70618 2023-12-03T06:15:15Z 2023-12-03T06:15:15Z <p>I saw a proof that claimed if the 3sat problem was statistically random which by definition means there are no patterns, then a deterministic turing machine could not possibly solve it more efficiently than a nondeterministic turing machine, as the problem itself was created nondeterministically. he then proceeded to create such a version of the 3sat problem.</p> <p>I made a post asking if his proof was wrong with a link too it and just got a few rhetorical answers basically saying it is to simple to possibly prove P does not equal NP.</p> <p>if anyone wants to see his actual work. <a href="https://www.academia.edu/110240103/how_statistical_randomness_disproves_P_NP" rel="nofollow noreferrer">https://www.academia.edu/110240103/how_statistical_randomness_disproves_P_NP</a></p> https://cstheory.stackexchange.com/q/53611 -6 I found a fascinating solution to P=NP on academia.edu, where he creates an inherently undeterministic problem using statistical randomness ChadTheVlad https://cstheory.stackexchange.com/users/70618 2023-12-03T01:46:54Z 2023-12-03T06:01:44Z <p>for background I just started researching computational complexity, so I have major gaps in understanding. I am not 100% sure if this guy is correct, but I can't seem to see why he would be wrong. could you guys tell me your thoughts, or why it is wrong so I can see where my gaps in understanding are.</p> <p>here is the link to the proposed solution.</p> <p><a href="https://www.academia.edu/110240103/how_statistical_randomness_disproves_P_NP" rel="nofollow noreferrer">https://www.academia.edu/110240103/how_statistical_randomness_disproves_P_NP</a></p> <p>I can't find an obvious problem with it.</p> <p>also go easy on my stupidity, I just started learning about computational complexity and don't fully understand it. or if it is an already explored and &quot;forbidden&quot; method of proving P does not equal NP</p> <p>thank you.</p> <p>update-so far no ones explained why it's wrong and have just given strange rhetorical answers, can someone please give me an actual answer.</p> https://cstheory.stackexchange.com/q/53608 0 Any analogues to Turing-Church thesis out there? [closed] aleksandar https://cstheory.stackexchange.com/users/70608 2023-12-01T17:15:10Z 2023-12-04T10:01:52Z <p>So the Turing-Church thesis says that computation formalisms such as Lambda Calculus and Turing Machine correspond to our <em>informal</em> notion of algorithm. It cannot be proven because it says that the Turing Machine is the best formal approximation of an &quot;algorithm&quot; that can be made. As pointed out in the comments, the thesis could be seen as a thesis about what computers can be built in the physical world, making it a thesis about the real world.</p> <p>Whenever there's a formalism to describe some aspect of the world around us (e.g. geometry that describes space), there's an implicit assumption that the reality corresponds well to that formalism. For most formalisms, we don't explicitly state that. Well, the act of proposing the formalism is basically such a statement.</p> <p>Yet, in the case of the notion of algorithm, we needed to make that correspondence explicit and that is the Turing-Church thesis.</p> <p>Therefore these questions are warranted:</p> <ul> <li>Are there other examples, unrelated to computation or computers, where it makes sense to make such an explicit thesis (analogous to the Turing-Church thesis)? Or T-C is a lonely creature?</li> <li>Bonus: why is it that in this context, we do have this <em>explicit</em> thesis, and in other contexts (say in other parts of physics) we don't?</li> </ul> https://cstheory.stackexchange.com/q/53607 1 Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog? Justin Lubin https://cstheory.stackexchange.com/users/70607 2023-12-01T17:04:08Z 2023-12-01T17:10:32Z <p><strong>Background</strong>: In the context of Datalog, <a href="https://dl.acm.org/doi/10.1145/1265530.1265535" rel="nofollow noreferrer">Green et. al (2007)</a> introduce the notion of the <em>Datalog provenance semiring</em>, a generalization of why-provenance as well as bag and probabilistic database semantics in which each EDB tuple is tagged with a symbolic value and combined via the operations of a commutative semiring. They call this form of provenance &quot;how-provenance&quot; because it shows <em>how</em> each EDB contributes to a derived fact.</p> <p>Sometimes, though, the &quot;how-provenance&quot; of a derived fact is defined as its <em>set of derivation trees</em>, for example by <a href="https://dl.acm.org/doi/10.14778/2824032.2824039" rel="nofollow noreferrer">Deutch et. al (2015)</a>.</p> <p>When the number of derivation trees is finite, the semiring provenance of a derived fact is the sum over all its derivation trees of the product of the tags of the leaves of the tree.</p> <p><strong>Question:</strong> Is it possible to go in the other direction—that is, to recover the set of derivation trees from the semiring provenance? And does the answer change if there are a finite or infinite number of derivation trees?</p> <p>To do so, I think you would need to modify the Datalog program so that each relation is tagged with an EDB that represents an identifier for that rule. But even then, the commutativity of the provenance semiring seems to make it difficult to reconstruct proof trees because you lose the order of derivations and leaves.</p> https://cstheory.stackexchange.com/q/53605 5 Variation of (derandomized) Valiant-Vazirani Noel Arteche https://cstheory.stackexchange.com/users/53377 2023-12-01T11:11:42Z 2023-12-01T11:11:42Z <p>I am interested in the following &quot;improvement&quot; of the Valiant-Vazirani reduction. As pointed out <a href="https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani">here</a>, under the right derandomization assumptions one can obtain a deterministic polynomial-time algorithm <span class="math-container">$R$</span> such that <span class="math-container">$R(\varphi) = (\psi_1, \dots, \psi_k)$</span> with <span class="math-container">$k$</span> polynomial in the size of <span class="math-container">$\varphi$</span>, such that</p> <ul> <li>if <span class="math-container">$\varphi$</span> is satisfiable, then at least one of the <span class="math-container">$\psi_i$</span> has exactly one satisfying assignment;</li> <li>if <span class="math-container">$\varphi$</span> is unsatisfiable, then every <span class="math-container">$\psi_i$</span> is unsatisfiable.</li> </ul> <p>Looking at the existing proofs of the Valiant-Vazirani lemma (Arora-Barak, and some lecture notes online), they all use the pairwise independent hashing over either <span class="math-container">$GF(2)^n$</span> or <span class="math-container">$GF(2^n)$</span>. My problem is that, as far as I can tell, in both of these setups when <span class="math-container">$\varphi$</span> is satisfiable, some of the formulas in <span class="math-container">$\psi_i$</span> might have multiple satisfying assignments -- it's just that one particular <span class="math-container">$\psi_i$</span> is guaranteed to have exactly one. I want to avoid this.</p> <p><strong>My question:</strong> Is it possible to obtain (possibly with a different family of hashing functions) a reduction where</p> <ul> <li>if <span class="math-container">$\varphi$</span> is satisfiable, <strong>then all the <span class="math-container">$\psi_i$</span> have at most one satisfying assignment</strong>, and at least one of the <span class="math-container">$\psi_i$</span> is satisfiable;</li> <li>if <span class="math-container">$\varphi$</span> is unsatisfiable, then every <span class="math-container">$\psi_i$</span> is unsatisfiable.</li> </ul> <p>I know that <a href="https://eccc.weizmann.ac.il//report/2011/151/" rel="noreferrer">different improvements on Valiant-Vazirani are unlikely</a>, but this variation doesn't seem to be ruled out by those results, or at least I couldn't see that. Is it known whether this reduction is possible?</p> https://cstheory.stackexchange.com/q/53604 0 Hardness for find the clause for statisfiable 3-SAT problems ironmanaudi https://cstheory.stackexchange.com/users/55982 2023-12-01T06:31:00Z 2023-12-01T06:31:00Z <p>The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as the condition given by the Lovasz local lemma (LLL). When the LLL is met, it is suggested that a feasible assignment to the variables can be found efficiently and an exemplified polynomial time algorithm is first proposed by <a href="https://dl.acm.org/doi/10.1145/1667053.1667060" rel="nofollow noreferrer">Moser and Tordos</a>. Therefore, my question is does knowing the answer to the decision problem (i.e., 3-SAT) help lower the complexity of the corresponding searching problem (i.e., finding the satisfiable assignment)? Or, on the other hand, the problem is still NP-hard.</p> <p>PS: the answer to the 3-SAT problem may be provided by an oracle.</p> https://cstheory.stackexchange.com/q/53603 -2 Proof that DFS order is P-complete Robin Petr https://cstheory.stackexchange.com/users/70600 2023-11-30T21:00:56Z 2023-12-03T11:47:38Z <p>Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm on the given graph, where we search through the edges in the specified order, we get the particular order in which the vertices are visited.</p> <p>How can I prove that U gets visited before V? And why it's a P-complete problem.</p> <p>I know it's a P-complete problem, I have read through this article: <a href="https://sci-hub.se/10.1016/0020-0190(85)90024-9" rel="nofollow noreferrer">https://sci-hub.se/10.1016/0020-0190(85)90024-9</a></p> <p>but I still don't get it</p> https://cstheory.stackexchange.com/q/53602 3 How often can a clause cause a conflict? Russell Easterly https://cstheory.stackexchange.com/users/4881 2023-11-30T18:40:59Z 2023-12-06T20:32:28Z <p>This question is about <a href="https://en.wikipedia.org/wiki/Conflict-driven_clause_learning" rel="nofollow noreferrer">DPLL+CDCL algorithms</a>. How often can a clause cause a conflict?</p> <p>I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit clauses are processed from highest order to lowest order. Positive literals are processed before negative literals. For example, if there are multiple unit clauses to be processed then the unit clause with the highest order variable is processed first. If there is both a positive and negative unit clause with this highest order variable then the positive literal is processed first.</p> <p>One decision variable is set at a time and then all unit clauses are processed one at a time until a conflict is found. When a conflict is found a new learned clause is created. Unlike most CDCL solvers which use first implication learned clauses, assume this solver always creates a learned clause using decision variables.</p> <p>Since the algorithm processes variables one at a time, any clause that causes a conflict must have been a unit clause before the conflict. Since all unit clauses are processed after every decision variable is set, conflicts can only be caused by processing unit clauses, not by setting a decision variable. This is why I specify the order for processing unit clauses.</p> <p>By design, when a decision variable is chosen and given a value, all higher order variables must have been assigned a value either as decision variables or because of processing unit clauses. This means the last variable in the unit clause that causes the conflict must be lower order than the decision variable.</p> <p>When a clause causes a conflict, a new learned clause will be created. All of the variables in this new learned clause must be higher than the lowest order variable is the first (conflicted) clause.</p> <p>Can I say that a clause can not cause a conflict more than N times, where N is the number of variables in the instance? If not, why not?</p> https://cstheory.stackexchange.com/q/53601 1 Find the SVM kernel in detecting if a substring in a given string Tran Khanh https://cstheory.stackexchange.com/users/70416 2023-11-28T04:29:42Z 2023-11-28T11:06:32Z <p>Consider the task of learning to find a sequence of characters (&quot;signature&quot;) in a file that indicates whether it contains a virus or not and let <span class="math-container">$\mathcal{X}$</span> be the set of all finite strings over some alphabet set <span class="math-container">$\Sigma$</span>, and let <span class="math-container">$\mathcal{X}_d$</span> be the set of all such strings of length at most <span class="math-container">$d$</span>. The learning hypothesis class is <span class="math-container">$\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$</span>, where, for a string <span class="math-container">$x\in\mathcal{X}$</span>, <span class="math-container">$h_v(x)$</span> is <span class="math-container">$1$</span> iff <span class="math-container">$v$</span> is a substring of <span class="math-container">$x$</span> (and <span class="math-container">$h_v(x) = −1$</span> otherwise).</p> <p>Let <span class="math-container">$s = |\mathcal{X}_d|$</span> and consider a mapping <span class="math-container">$\psi$</span> to a space <span class="math-container">$\mathbb{R}^s$</span>, so that each coordinate of <span class="math-container">$\psi (x)$</span> corresponds to some string <span class="math-container">$v$</span> and indicates whether <span class="math-container">$v$</span> is a substring of <span class="math-container">$x$</span> (that is, for every <span class="math-container">$x \in \mathcal{X}, \psi(x)$</span> is a vector in <span class="math-container">$\lbrace 0,1\rbrace^{|\mathcal{X}_d|}$</span>). Note that the dimension of this feature space is exponential in <span class="math-container">$d$</span>.</p> <p>Given that information, I need to show that every member of the class <span class="math-container">$\mathcal{H}$</span> can be realized by composing a linear classifier over <span class="math-container">$\psi (x)$</span>, and, moreover, by such a halfspace whose norm is 1 and that attains a margin of 1.</p> <p>However, I was confused over the <span class="math-container">$v$</span> in the definition of <span class="math-container">$\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$</span>. My understanding is that this <span class="math-container">$v$</span> denotes any string <span class="math-container">$v\in\mathcal{X}_d$</span> not just some fixed string. Suppose my understanding is correct then denote by <span class="math-container">$v_1, v_2,..., v_s$</span> all strings in <span class="math-container">$\mathcal{X}_d$</span> and then we can define <span class="math-container">$\psi$</span> by</p> <p><span class="math-container">$$\psi(x) = \begin{bmatrix} h_{v_1}(x) \\ h_{v_s}(x) \\ \vdots \\ h_{v_s}(x) \end{bmatrix}.$$</span></p> <p>Thus we have <span class="math-container">$h_{v_i}(x)=\psi (x)_i$</span> (the i(th)-element of <span class="math-container">$\psi (x)$</span>). But I don't see any the linear classifiers in this equation let alone the margin and the norm constraints?</p> https://cstheory.stackexchange.com/q/53600 -1 corresponding resoving and arbitary resolving Jxb https://cstheory.stackexchange.com/users/66233 2023-11-28T03:00:45Z 2023-11-28T03:00:45Z <p><strong>Notations</strong>:</p> <p><span class="math-container">$$C_x \otimes C_{\bar{x}} = V_1 \lor \ldots \lor V_a \lor W_1 \lor \ldots \lor W_b$$</span> <span class="math-container">$$\text{ where } C_x = x \lor V_1 \lor \ldots \lor V_a \text{ and } C_{\bar{x}} = \bar{x} \lor W_1 \lor \ldots \lor W_b$$</span></p> <p>I'm delving into the topic of variable elimination in SAT preprocessing, and I've encountered a conceptual challenge concerning the resolution of clauses with a variable <span class="math-container">$x$</span> and its negation <span class="math-container">$\bar{x}$</span>. For context, let <span class="math-container">$S_x$</span> represent the set of clauses containing <span class="math-container">$x$</span> and <span class="math-container">$S_{\bar{x}}$</span> the set containing <span class="math-container">$\bar{x}$</span>, with each set comprising exactly <span class="math-container">$n$</span> clauses.</p> <p><span class="math-container">$S_x = \{ C^1_x,...,C^n_x \}$</span></p> <p><span class="math-container">$S_{\bar{x}} = \{ C^1_{\bar{x}},...,C^n_{\bar{x}} \}$</span></p> <p><strong>Now, onto my question:</strong> If we consider the pairwise resolution between each clause in <span class="math-container">$S_x$</span> and the corresponding clause in <span class="math-container">$S_{\bar{x}}$</span>, does this result in a set of resolvents that is logically equivalent to the set of all possible resolvents formed by resolving every clause in <span class="math-container">$S_x$</span> with every clause in <span class="math-container">$S_{\bar{x}}$</span>?</p> <p>Formally, if <span class="math-container">$\{C_x \otimes C_{\bar{x}} \mid C_x \in S_x, C_{\bar{x}} \in S_{\bar{x}}\}$</span> is equivalent to <span class="math-container">$\{C^i_x \otimes C^i_{\bar{x}} \mid C^i_x \in S_x, C^i_{\bar{x}} \in S_{\bar{x}}\}$</span>?</p> <p>To clarify, by 'corresponding clauses,' I mean taking each clause <span class="math-container">$C^i_x$</span> from <span class="math-container">$S_x$</span> and resolving it with a clause <span class="math-container">$C^i_{\bar{x}}$</span> from <span class="math-container">$S_{\bar{x}}$</span>, where <span class="math-container">$C^i_x$</span> and <span class="math-container">$C^i_{\bar{x}}$</span> are matched based on their index in their respective sets. Is this restricted set of resolvents logically equivalent to the comprehensive set obtained by considering all possible combinations of clauses from <span class="math-container">$S_x$</span> and <span class="math-container">$S_{\bar{x}}$</span>?</p> https://cstheory.stackexchange.com/q/53598 8 What can we do with a generic oracle (as opposed to a random one)? Gro-Tsen https://cstheory.stackexchange.com/users/17747 2023-11-27T15:24:57Z 2023-11-29T08:16:26Z <p>Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):</p> <ul> <li><p><strong>Standard definitions:</strong> A subset <span class="math-container">$N \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is said to be <strong>null</strong> (= “of measure <span class="math-container">$0$</span>”) when for all <span class="math-container">$\varepsilon&gt;0$</span> there is a finite-or-infinite sequence <span class="math-container">$(w_n)$</span> of finite words <span class="math-container">$w_n \in \lbrace 0,1\rbrace^ *$</span> such that <span class="math-container">$N \subseteq \bigcup_n B_{w_n}$</span> and <span class="math-container">$\sum_n 2^{-\ell(w_n)} &lt; \varepsilon$</span> where <span class="math-container">$B_{w_n} \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> denotes the set of binary sequences having <span class="math-container">$w_n$</span> as prefix. A subset <span class="math-container">$M \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is said to be <strong>meager</strong> (= “of first category”) when there is a finite-or-infinite sequence <span class="math-container">$(R_n)$</span> of subsets <span class="math-container">$R_n \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> such that <span class="math-container">$M \subseteq \bigcup_n R_n$</span> and <span class="math-container">$R_n$</span> is nowhere dense (= “rare”) in the sense that for every finite word <span class="math-container">$w \in \lbrace 0,1\rbrace^ *$</span> there is a finite extension <span class="math-container">$w'$</span> of <span class="math-container">$w$</span> such that <span class="math-container">$B_{w'} \cap R_n = \varnothing$</span>. We say that a set is <strong>of full measure</strong> when its complement is null, and <strong>comeager</strong> when its complement is meager.</p> </li> <li><p>Recall that there is a large amount of parallelism between the two notions: a theme that is explored, for example, in Oxtoby's classic book <em>Measure and Category</em> (1980). Both “null” and “meager” are notions of smallness, and both are closed under countable unions. However, they are also in a sense opposed: for example, the set of binary sequences <span class="math-container">$b \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> such that the average proportion of <span class="math-container">$1$</span>'s in the <span class="math-container">$n$</span> first bits <span class="math-container">$\rho_n := \frac{1}{n}\sum_{k=0}^{n-1} b_k$</span> does not tend to <span class="math-container">$\frac{1}{2}$</span> is null (i.e., from the measure point of view, “almost all” sequences have <span class="math-container">$\lim_n \rho_n = \frac{1}{2}$</span>) whereas that same set is meager (i.e., from the category point of view, “generically all” sequences do <em>not</em> have this property, in fact, on a comeager set, <span class="math-container">$\limsup_n \rho_n = 1$</span> and <span class="math-container">$\liminf_n \rho_n = 0$</span>). In particular, <span class="math-container">$\lbrace 0,1\rbrace^{\mathbb{N}}$</span> is the union of a null and a meager set.</p> </li> <li><p>A perhaps not so well-known <strong>fact ① from computability</strong>: if <span class="math-container">$L \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq_{\mathrm{T}}} A \rbrace$</span> is of full measure (or, indeed, when it is not null), then in fact <span class="math-container">$L$</span> is computable. Here, <span class="math-container">$\mathrel{\leq_{\mathrm{T}}}$</span> denotes Turing-reducibility (in fact, by countable additivity, we might as well assume that the same oracle machine does the reduction in every case). In other words, “a non-trivial Turing upper cone is null”. In other words, “if <span class="math-container">$L$</span> is computable by a non-null set of oracles, then it is computable”. References for this fact: Sacks, <em>Degrees of Unsolvability</em> (1963), §10, theorem 1 (p. 154); Nies, <em>Computability and Randomness</em> (2009), theorem 5.1.12 (p. 169); or Downey &amp; Hirschfeldt, <em>Algorithmic Randomness and Complexity</em> (2010), corollary 8.2.12 (p. 358).</p> </li> <li><p>The dual (and perhaps even less well known) <strong>fact ② from computability</strong>: if <span class="math-container">$L \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq_{\mathrm{T}}} A \rbrace$</span> is comeager (or, indeed, when it is not meager), then in fact <span class="math-container">$L$</span> is computable. (Again, we might as well assume that the same oracle machine does the reduction in every case.) In other words, “a non-trivial Turing upper cone is meager”. In other words, “if <span class="math-container">$L$</span> is computable by a non-meager set of oracles, then it is computable”. References for this fact: Hinman, <em>Recursion-Theoretic Hierarchies</em> (1978), theorem II.5.3 (p. 63); or Cooper, <em>Computability Theory</em> (2004), example 13.2.21 (p. 283).</p> </li> <li><p>If <span class="math-container">$X$</span> is a relativizable complexity class of decision problems, the class <span class="math-container">$\textbf{Almost}X$</span> is defined as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$</span> is of full measure. Among the standard identities are the fact that <span class="math-container">$\textbf{AlmostP} = \textbf{BPP}$</span>, <span class="math-container">$\textbf{AlmostNP} = \textbf{AM}$</span> and <span class="math-container">$\textbf{AlmostPSPACE} = \textbf{BP}^{\exp}\,\textbf{PSPACE}$</span>: see <a href="https://blog.computationalcomplexity.org/2023/03/identities-in-computational-complexity.html" rel="noreferrer">this blog post by Josh Grochow</a> for references. Note that, “fact ①” above can be rephrased as “<span class="math-container">$\textbf{AlmostComputable} = \textbf{Computable}$</span>”.</p> </li> </ul> <p>I'm sure everyone can see where I'm going now:</p> <ul> <li><strong>Definition</strong> (mine, non-standard): if <span class="math-container">$X$</span> is a relativizable complexity class of decision problems, define the class <span class="math-container">$\textbf{Generically}X$</span> as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$</span> is comeager. Note that, “fact ②” above can be rephrased as “<span class="math-container">$\textbf{GenericallyComputable} = \textbf{Computable}$</span>”.</li> </ul> <p>✱ <strong>Warning:</strong> It is tempting to express “<span class="math-container">$\textbf{Almost}X$</span>” as “<span class="math-container">$X$</span> with respect to a random oracle” and “<span class="math-container">$\textbf{Generically}X$</span>” as “<span class="math-container">$X$</span> with respect to a generic oracle”. (Indeed, this is how I think of them intuitively.) This is, however, potentially confusing, because there are absolutely defined notions of “random” and “generic”, and in fact many variations on what “random” and “generic” mean (even though the common theme is “does not belong to any computable-in-some-sense null set”, resp. “does not belong to any computable-in-some-sense meager set”). See <a href="https://cstheory.stackexchange.com/q/25995/17747">this other question</a> and the answers to it concerning “random”, but the same points can be made concerning “generic”. (In the context of set theory, see Jech, <em>Set Theory (Third Millennium Edition)</em> lemma 26.4 (p. 514) for a characterization of (forcing-)random reals and (Cohen-forcing-)generic reals along these lines.) So I prefer to refrain speaking of “random” and “generic” oracles in the actual question, but it is also impossible <em>not</em> to make the point, and I took the liberty to use it in the “generic oracle” terminology in the title of the question.</p> <p><strong>QUESTIONS:</strong> Having defined <span class="math-container">$\textbf{GenericallyP}$</span> as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in \textbf{P}^A \rbrace$</span> is comeager, let me ask the following:</p> <ul> <li><p>Is <span class="math-container">$\textbf{GenericallyP}$</span> equal to a standard complexity class (e.g., one in the Complexity Zoo)? Has it received another name? Has it been studied? Can we say anything non-trivial about it?</p> </li> <li><p>Can we identify a problem in <span class="math-container">$\textbf{GenericallyP}$</span> that is conjecturally not not in <span class="math-container">$\textbf{P}$</span>, or even “not obviously” in <span class="math-container">$\textbf{P}$</span>? Or is it reasonable to conjecture that <span class="math-container">$\textbf{GenericallyP} = \textbf{P}$</span>?</p> </li> <li><p>Soft question: intuitively speaking, what might a “pseudogeneric” sequence generator even look like? (I can make some sense of “pseudorandom” because randomness lends itself quite well to finite approximations, but “pseudogeneric” seems much more slippery: as noted above, whereas pseudorandom sequences obey the law of large numbers, pseudogeneric ones avoid all such laws. And conversely, whereas I can imagine how to make <em>use</em> of a random oracle, making use of a generic oracle seems almost unthinkable: but I'd be happy to be proved wrong here.)</p> </li> </ul> https://cstheory.stackexchange.com/q/53596 5 Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula? Jxb https://cstheory.stackexchange.com/users/66233 2023-11-27T06:47:51Z 2023-11-27T09:21:05Z <p>I have a question regarding the Conflict-Driven Clause Learning (CDCL) algorithm applied to an unsatisfiable CNF formula <span class="math-container">$F$</span>.</p> <p><strong>Specifically, can all the conflict clauses learned by the CDCL algorithm be derived from the original formula <span class="math-container">$F$</span> through resolution?</strong></p> <p>I believe the answer should be affirmative. My reasoning is that if this were not the case, I would have trouble understanding why the general resolution size of <span class="math-container">$F$</span> can serve as a lower bound for the runtime of the CDCL algorithm. However, I'm seeking clarification or confirmation on this point.</p> <p>Could someone provide insights or references that confirm or refute this understanding? Thank you!</p> https://cstheory.stackexchange.com/q/53594 -1 Proof for Upper Bound on the Size of the Sum of Rational Numbers Arcade_TryHard https://cstheory.stackexchange.com/users/70563 2023-11-25T22:23:18Z 2023-11-25T22:23:18Z <p>In , Dominik Wojtczak determines that the 0-1 SUBSET-SUM problem with non-negative rational numbers is strongly NP-Complete.</p> <blockquote> <p>Assume we are given a list of n items with rational non-negative weights A = {w1, . . . , wn} and a target total weight W ∈ Q≥0. 0-1 SUBSET SUM: Does there exist a subset B of A such that the total weight of B is equal to W? [...] Let A = {w1, . . . , wn} be an instance such that <span class="math-container">$w_i=\frac{a_i}{b_i}$</span> where <span class="math-container">$a_i, b_i$</span> ∈ N for all i = 1, . . . , n.</p> </blockquote> <p>That implies that the problem is in NP thus can be verified in polynomial time, which means that summing rational numbers can be done in polynomial time(in fact in O(n^2) operations). Since the problem is strongly NP-Complete, assuming P ≠ NP, no algorithm can solve all instances in time polynomial in the size of the problem (<span class="math-container">$Θ(\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i)$</span> <strong>in unary</strong> and <span class="math-container">$Θ(\sum_{i=1}^{n}log(a_i)+\sum_{i=1}^{n}log(b_i))$</span> <strong>in binary</strong>).</p> <blockquote> <p>We can then simply verify whether <span class="math-container">$\sum_{i=1}^{n}q_i*a_i=W$</span> holds in polynomial time by adding the rational numbers inside this sum one by one (while representing all the numerators and denominators in binary).</p> </blockquote> <p>Out of all possible sums, the maximum sum in the case of the 0-1 SUBSET SUM problem is the result of summing all the elements in the set. However, the author didn't give any upper bound for the size of the denominator and numerator <strong>before reducing the fraction</strong>. What is the upper bound for the denominator and the numerator in relation to the size of the problem in unary?</p> <p><strong>References</strong></p> <p> Dominik Wojtczak, <a href="https://arxiv.org/abs/1802.09465v1" rel="nofollow noreferrer">&quot;On Strong NP-Completeness of Rational Problems&quot;</a>, 2018</p> https://cstheory.stackexchange.com/q/53589 2 Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes? Johan Thiborg-Ericson https://cstheory.stackexchange.com/users/70162 2023-11-23T16:14:37Z 2023-11-28T05:36:14Z <p>In <a href="https://www.cambridge.org/us/universitypress/subjects/mathematics/logic-categories-and-sets/introduction-higher-order-categorical-logic" rel="nofollow noreferrer">Introduction to Higher Order Categorical Logic</a> part 1, section 4, Lambek defines an adjunction between <span class="math-container">$\mathbf{Graph}$</span>, the category of graphs and graph homomorphisms, and the category of Cartesian closed categories with a natural number object and Cartesian closed functors between them. Is there a similar adjunction between <span class="math-container">$\mathbf{Graph}$</span> and the category <span class="math-container">$\mathbf{Bicart}$</span> of bicartesian closed categories and bicartesian closed functors between them? If so, let <span class="math-container">$\operatorname{F} : \mathbf{Graph} \to \mathbf{Bicart}$</span> be the Free functor of that adjunction.</p> <p>Let</p> <ul> <li><span class="math-container">$(* \to)^0 *$</span> denote the kind <span class="math-container">$*$</span>,</li> <li><span class="math-container">$(* \to)^1 *$</span> denote the kind <span class="math-container">$* \to *$</span>,</li> <li><span class="math-container">$(* \to)^2 *$</span> denote the kind <span class="math-container">$* \to * \to *$</span>,</li> </ul> <p>and so on. Further, for each <span class="math-container">$n \ge 0$</span>, let <span class="math-container">$g_n$</span> be a discrete graph with <span class="math-container">$n$</span> nodes. For each <span class="math-container">$n$</span>, do the types of kind <span class="math-container">$(* \to)^n *$</span>, and all polymorphic functions between them, form a category? Is this category (isomorphic to) <span class="math-container">$\operatorname{F} g_n$</span>?</p> https://cstheory.stackexchange.com/q/53584 6 Error in Robson's proof about separating strings? domotorp https://cstheory.stackexchange.com/users/419 2023-11-22T10:02:22Z 2023-11-28T11:37:13Z <p>One of my students discovered a possible mistake in Robson's classic paper <a href="https://doi.org/10.1016/0020-0190(89)90215-9" rel="noreferrer">Separating strings with small automata</a>.<br /> The issue is in the proof of Theorem 1, giving the simpler bound <span class="math-container">$O(\sqrt{n\log n})$</span>.<br /> The proof goes by giving an automaton that finds a substring of length <span class="math-container">$O(\sqrt{n\log n})$</span> in <span class="math-container">$u$</span> that ends in <span class="math-container">$i$</span> such that <span class="math-container">$u_i\ne v_i$</span> is the first place where the words <span class="math-container">$u$</span> and <span class="math-container">$v$</span> differ.<br /> It is correctly proved that the given substring cannot occur in <span class="math-container">$v$</span> up to <span class="math-container">$i$</span>, starting with some required modulo, but the issue is that the substring can arise after <span class="math-container">$i$</span>.<br /> I think that he is right, and see no way of saving the proof.</p> <p>ps. Note that the best claimed bound in Robson is <span class="math-container">$\tilde O(n^{2/5})$</span> recently a better bound, <span class="math-container">$\tilde O(n^{1/3})$</span> was proved by <a href="https://arxiv.org/abs/2007.12097" rel="noreferrer">Chase</a>.</p> https://cstheory.stackexchange.com/q/53503 2 Known Variant of Set Cover? Jan Reineke https://cstheory.stackexchange.com/users/70445 2023-11-08T19:40:36Z 2023-12-03T06:03:19Z <p>Consider the following variant of set cover:</p> <p>Given: Target set <span class="math-container">$T$</span> and a collection of sets <span class="math-container">$\mathcal{C}$</span>, such that <span class="math-container">$T \subseteq \bigcup_{C \in \mathcal{C}} C$</span>.</p> <p>Wanted: A subset <span class="math-container">$\mathcal{C'}$</span> of <span class="math-container">$\mathcal{C}$</span>, such that <span class="math-container">$T \subseteq \bigcup_{C \in \cal{C'}} C$</span> and <span class="math-container">$|\bigcup_{C \in \cal{C'}} C|$</span> is minimal.</p> <p>In other words, we are looking for a covering of <span class="math-container">$T$</span> that covers as few additional elements as possible.</p> <p>It is relatively easy to see that this problem is NP-complete.</p> <p>Is this a known problem? What is its name?</p> https://cstheory.stackexchange.com/q/53470 0 Representing/Modelling fields and methods in the context of programming as automata The Pointer https://cstheory.stackexchange.com/users/44297 2023-10-27T11:21:28Z 2023-11-26T21:02:30Z <p>I am trying to represent/model fields and methods in the context of programming as automata. For instance, let's say that I have <code>field1</code> with state equal to 2, <code>field2</code> with state equal to 3, and <code>method1</code> being the calculation <code>field2</code> <span class="math-container">$=$</span> <code>field1</code> <span class="math-container">$\times$</span> 2 <span class="math-container">$+$</span> <code>field2</code> <span class="math-container">$\times$</span> 3. If I represent <code>field1</code> as one automaton and <code>field2</code> as another automaton, <code>field1</code> would first change its state to <span class="math-container">$2 \times 2 = 4$</span> and then <code>field2</code> would change its state to <span class="math-container">$3 \times 3 = 9$</span>. But it isn't clear to me how one would then represent the interaction between these two automatons to make <code>field2</code> state equal to <span class="math-container">$4 + 9 = 13$</span> (since the automaton representing <code>field2</code> would need to retrieve the state value of the automaton representing <code>field1</code>), and nor is it clear to me how one would have the &quot;transience&quot;/&quot;temporary&quot; aspect, since <code>field1</code> would then have to revert back to state equal to <span class="math-container">$2$</span> (since the computation with regards to this field/automaton is temporary and not permanent).</p> <p>I suspect that this stuff has already been figured out, but I'm a fresh grad student, so I'm not really aware of this stuff.</p> https://cstheory.stackexchange.com/q/52633 0 Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm Ash https://cstheory.stackexchange.com/users/67746 2023-03-23T13:41:17Z 2023-12-01T11:45:11Z <p><span class="math-container">$\newcommand{\R}{\mathbb{R}}$</span> This question is about Problem 3.16 in Ryan O'Donnell's <em>Analysis of Boolean Functions</em> book. The problem is stated as follows:</p> <blockquote> <p>Let <span class="math-container">$f : \{-1,1\}^n\to\R$</span> and let <span class="math-container">$\epsilon&gt;0$</span>. Show that <span class="math-container">$f$</span> is <span class="math-container">$\epsilon$</span>-concentrated on a collection <span class="math-container">$F\subseteq 2^{[n]}$</span> with <span class="math-container">$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$</span>.</p> </blockquote> <p>Here, <span class="math-container">$\hat{||}f\hat{||}_1 := \sum_{S\subseteq [n]} |\widehat{f}(S)|$</span>, and <span class="math-container">$f$</span> being <span class="math-container">$\epsilon$</span>-concentrated on <span class="math-container">$F$</span> means <span class="math-container">$\sum_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$</span>. I have tried several approaches for this problem, and all seem to run into the pitfall of relating <span class="math-container">$\hat{||}f\hat{||}_1^2$</span> to <span class="math-container">$||f||_2$</span> (equivalently <span class="math-container">$\hat{||}f\hat{||}_2$</span> by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling <span class="math-container">$|\widehat{f}(S)|$</span> uniformly over <span class="math-container">$S$</span>, bounding the variance of this random variable, and applying Chebyshev's. But since <span class="math-container">$\mathbf{E}[|\widehat{f}(S)|]$</span> might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!</p> <p><strong>Edit:</strong> I was eventually able to find a solution. As a hint, start by constructing a reasonable set <span class="math-container">$F$</span> which trivially satisfies <span class="math-container">$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$</span>. To prove <span class="math-container">$\epsilon$</span>-concentration, recall the fairly simple technique used to bound <span class="math-container">$\sum \widehat{g}(S)^3$</span> in the analysis for the BLR test (Section 1.6 in <em>Analysis of Boolean Functions</em>).</p> https://cstheory.stackexchange.com/q/51685 3 Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function? Daniel Primosch https://cstheory.stackexchange.com/users/66212 2022-07-11T18:07:25Z 2023-12-03T22:06:35Z <p>The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, <span class="math-container">$N$</span>, increases. For the exponential distribution this specifically means that the relative variance, <span class="math-container">$var_{rel} = \frac{var(PDF)}{mean^2(PDF)}$</span>, of the PDF with increasing <span class="math-container">$N$</span> is constant (exactly <span class="math-container">$var_{rel}(N)=1$</span> actually) and the kurtosis is constant as well.</p> <p>Are there any algorithms whose relative variance in the PDF of the run-time distribution would be expected to decrease, specifically as <span class="math-container">$\sim \frac{1}{N}$</span>, and/or where the kurtosis decreases?</p> <p>This would seem intuitively strange to me since that would mean that the algorithm would become more &quot;deterministic&quot; (in the physics sense), but I want to make sure.</p> <p>Is there a straightforward interpretation of what it would mean for a non-trivial, competitive algorithm to exhibit such a trait of <span class="math-container">$var_{rel}\sim \frac{1}{N}$</span> and decreasing kurtosis?</p> https://cstheory.stackexchange.com/q/47932 33 Is Descriptive Complexity dead? Noel Arteche https://cstheory.stackexchange.com/users/53377 2020-11-27T15:51:50Z 2023-12-01T08:21:29Z <p>I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?</p> https://cstheory.stackexchange.com/q/46930 4 Online TCS Seminars Klim https://cstheory.stackexchange.com/users/1821 2020-05-26T16:14:58Z 2023-11-28T19:33:08Z <p>I want to have a list of online seminars that holds now. So far I know only about TCS+(<a href="https://www.tcsplus.org/" rel="nofollow noreferrer">https://www.tcsplus.org/</a>) seminars. I would like to ask if there are other TCS seminars.</p> https://cstheory.stackexchange.com/q/45920 2 About estimating escape time of gradient Langevin dynamics gradstudent https://cstheory.stackexchange.com/users/42159 2019-11-25T00:58:44Z 2023-12-06T03:08:31Z <p>I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper <a href="https://arxiv.org/abs/1902.08179" rel="nofollow noreferrer">https://arxiv.org/abs/1902.08179</a>. Let me summarize the conceptual crux of the argument here using a slightly different notation than them. </p> <p>Here we are given <span class="math-container">$F : \mathbb{R}^d \rightarrow \mathbb{R}$</span> a convex, differentiable and <span class="math-container">$L-$</span>smooth function with a minimizer at <span class="math-container">$x^*$</span> and 3 constants : <span class="math-container">$r$</span> and <span class="math-container">$C_\xi$</span> and <span class="math-container">$i_{max}$</span> (a positive integer). Now for <span class="math-container">$\xi_{t,1}$</span> a sequence of bounded random variables and <span class="math-container">$\xi_{t,2}$</span> a sequence of Normally distributed random variables we have the following dynamics happening, </p> <p><span class="math-container">$$x_{t+1} = x_t - \eta_t (\nabla F(x_t) + \xi_{t,1}) + \sqrt{\eta_t} \xi_{t,2}$$</span></p> <p>which starts from <span class="math-container">$x_0$</span> s.t <span class="math-container">$\Vert x_0 - x^* \Vert \leq r$</span> </p> <p>Now they consider a coupled toy Markov chain <span class="math-container">$x'_t$</span> s.t <span class="math-container">$x'_0 = x_0$</span> and,</p> <p><span class="math-container">$$\text{if } \Vert x_t' - x^* \Vert \geq r \text{ then } x'_{t+1} = x'_t$$</span> and <span class="math-container">$\text{if } \Vert x_t' - x^* \Vert &lt; r \text{ then } x'_{t+1} = x'_t - \eta_t (\nabla F(x_t') + \xi_{t,1}) + \sqrt{\eta_t} \min (C_\xi, \Vert \xi_{t,2} \Vert) \frac{\xi_{t,2}}{\Vert \xi_{t,2} \Vert}$</span></p> <p>Hence it seems that the primed sequence is designed s.t it never comes back into the ball once it leaves the interior of the <span class="math-container">$r$</span> sized ball around the global minimum of the function. </p> <ul> <li>Now the main technical claim they make to relate the primed and the unprimed sequence is this : say the event <span class="math-container">$E := \{ \exists i \in \{1,\ldots,i_{\max}\} s.t \Vert x_i - x^*\Vert &gt; r\}$</span> then some curious union bounding is giving them,</li> </ul> <p><span class="math-container">$$\mathbb{P} \left [ E \right ] \leq \sum_{i=1}^{i_{max}} \left ( \mathbb{P} [\Vert x_i'-x^*\Vert^2 \geq r^2] + \mathbb{P} [ \Vert \xi_{i,2} \Vert \geq C_\xi ] \right )$$</span></p> <p>Can someone kindly explain why is the above inequality true?</p> https://cstheory.stackexchange.com/q/13950 55 Good examples for how to write well in TCS Suresh Venkat https://cstheory.stackexchange.com/users/80 2012-10-15T00:03:44Z 2023-11-28T17:13:47Z <p>I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples off the top of my head</p> <blockquote> <p>What are the best examples of quality mathematical writing you've seen ?</p> </blockquote> <p>Rules:</p> <ul> <li>I'd prefer TCS papers as far as possible. Our style is different enough from standard math papers that I think it's better to focus on TCS (also why I'm asking here and not on MO)</li> <li>it would help if you mentioned what exactly you thought the paper did well. Not all exposition is good at everything - some papers have great proof outlines, some use notation really effectively and others convey intuition masterfully. </li> <li>if possible, please link to the paper. </li> </ul> <p>I'm hoping this can become a resource, like many of our other broad questions. I'm marking it CW for that reason. </p> https://cstheory.stackexchange.com/q/6404 23 Survey on #P and/or counting problems Tayfun Pay https://cstheory.stackexchange.com/users/1590 2011-05-05T00:07:57Z 2023-12-06T03:08:50Z <p>Can anyone suggest a good and recent survey on counting problems and/or problems that are #P. </p>