All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
4 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
rus9384's user avatar
  • 245
-3 votes
0 answers
28 views

would statistical randomness disprove P=NP

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 ...
ChadTheVlad's user avatar
-6 votes
0 answers
58 views

I found a fascinating solution to P=NP on academia.edu, where he creates an inherently undeterministic problem using statistical randomness

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. ...
ChadTheVlad's user avatar
0 votes
1 answer
158 views

Does Turing-Church thesis have a secret life? [closed]

So the Turing-Church thesis says that computation formalisms such as Lambda Calculus and Turing Machine correspond to our informal notion of algorithm. It cannot be proven because it since it says ...
aleksandar's user avatar
1 vote
0 answers
52 views

Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

Background: In the context of Datalog, Green et. al (2007) introduce the notion of the Datalog provenance semiring, a generalization of why-provenance as well as bag and probabilistic database ...
Justin Lubin's user avatar
5 votes
0 answers
89 views

Variation of (derandomized) Valiant-Vazirani

I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
Noel Arteche's user avatar
0 votes
0 answers
46 views

Hardness for find the clause for statisfiable 3-SAT problems

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 ...
ironmanaudi's user avatar
-1 votes
0 answers
50 views

Proof that DFS order is P-complete

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 ...
Robin Petr's user avatar
1 vote
0 answers
57 views

How often can a clause cause a conflict?

This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict? I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
Russell Easterly's user avatar
1 vote
0 answers
38 views

Find the SVM kernel in detecting if a substring in a given string

Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite ...
Tran Khanh's user avatar
-1 votes
0 answers
32 views

corresponding resoving and arbitary resolving

Notations: $$C_x \otimes C_{\bar{x}} = V_1 \lor \ldots \lor V_a \lor W_1 \lor \ldots \lor W_b$$ $$ \text{ where } C_x = x \lor V_1 \lor \ldots \lor V_a \text{ and } C_{\bar{x}} = \bar{x} \lor W_1 \lor ...
Jxb's user avatar
  • 315
8 votes
1 answer
389 views

What can we do with a generic oracle (as opposed to a random one)?

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): Standard definitions: A ...
Gro-Tsen's user avatar
  • 619
5 votes
1 answer
148 views

Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?

I have a question regarding the Conflict-Driven Clause Learning (CDCL) algorithm applied to an unsatisfiable CNF formula $F$. Specifically, can all the conflict clauses learned by the CDCL algorithm ...
Jxb's user avatar
  • 315
-1 votes
0 answers
81 views

Proof for Upper Bound on the Size of the Sum of Rational Numbers

In [1], Dominik Wojtczak determines that the 0-1 SUBSET-SUM problem with non-negative rational numbers is strongly NP-Complete. Assume we are given a list of n items with rational non-negative ...
Arcade_TryHard's user avatar
2 votes
0 answers
71 views

Enforcing general position in $2d$ linear programming

Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$. I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
user3508551's user avatar
  • 1,078
2 votes
0 answers
53 views

Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?

In Introduction to Higher Order Categorical Logic part 1, section 4, Lambek defines an adjunction between $\mathbf{Graph}$, the category of graphs and graph homomorphisms, and the category of ...
Johan Thiborg-Ericson's user avatar
4 votes
0 answers
118 views

Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?

In Nemirovxki's lecture notes on interior point methods, I found the following. He defines an approximate solution as satisfying the following, for any given $\epsilon>0$: that is: the ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
41 views

Approximation ratio of randomized rounding for integral multi-commodity flow

In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
Recursion's user avatar
6 votes
2 answers
428 views

Error in Robson's proof about separating strings?

One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata. The issue is in the proof of Theorem 1, giving the simpler bound $O(\sqrt{n\log n})$. ...
domotorp's user avatar
  • 13.9k
2 votes
0 answers
58 views

Many-one equivalence of sets that differ finitely

[This is a duplicate of my question from Mathematics Stack Exchange: https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely I am posting it here since it ...
ijon's user avatar
  • 33
-2 votes
0 answers
46 views

d-regular graphs and edge expanders

Show that there is no (n, d, ρ)-edge expander for ρ > 0.5 Is this statement even true? My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
math-nerd-in-cs's user avatar
-2 votes
0 answers
43 views

Greedy rounding technique

I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for ...
LyLa's user avatar
  • 1
16 votes
2 answers
1k views

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
Junqiang Peng's user avatar
1 vote
1 answer
126 views

Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

For example, one that brains appear to be able to solve in polynomial time but computers can't, or one optimized for the brain's innate capabilities - like language learning, or different ...
soairse's user avatar
  • 11
-1 votes
0 answers
64 views

What are you favorite techniques at finding lower bounds?

I know that for finding lower bounds there are information-theoretic techniques like Le Cam's Two point method, Fano inequality and Assouad, other approaches use packing number. Is there a "...
rivana's user avatar
  • 53
-2 votes
1 answer
60 views

What is really the difference between membership queries and "querying in i.i.d?

I'm struggling at finding the difference between algorithms that use i.i.d random queries then request their labels and algorithms that use membership queries. Membership queries allow the learner to ...
Ayoubayjx's user avatar
  • 122
0 votes
1 answer
102 views

Confusion about lower bounds and upper bounds in learning theory

In computer science, lower bounds and upper bounds are defined as follow: $$m \geq g(n) \implies m = \Omega(g(n))$$ $$m \leq g(n) \implies m = \mathcal{O}(g(n))$$ However, in proving lower bounds and ...
rivana's user avatar
  • 53
0 votes
0 answers
92 views

Relationships between problem symmetry and its complexity

I read once that the more a problem has some symmetries the "easier" it is to solve and in particular its (time) complexity is polynomial. Conversely, when starting from a polynomial problem,...
deb2014's user avatar
-1 votes
0 answers
26 views

Finding an algorithm EF[1,1] and PO division for more than two agents

From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents. We consider the problem of fairly and efficiently ...
S. M.'s user avatar
  • 99
2 votes
2 answers
433 views

Technical limitations of Turing machines due to the input and output encoding of values

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
Gro-Tsen's user avatar
  • 619
1 vote
1 answer
100 views

Balanced set coloring

Let $\{S_1, S_2, ..., S_m\}$ be a collection of subsets of some universe $U$, where each $S_i$ has even size (so does $U$). We want to color the elements of $U$, either red or blue, such that each $...
Arnaud Casteigts's user avatar
-1 votes
0 answers
50 views

Average case complexity of decision version of NP-hard problem

I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
Subhra Mazumdar's user avatar
1 vote
0 answers
39 views

what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?

Is there some known lower bounds for estimating large fourier coefficients of boolean functions? And were there any comparison of tightness with the upper bound of Goldreich Levin algorithm?
rivana's user avatar
  • 53
4 votes
1 answer
142 views

Connection between strong normalization of the simply typed λ-calculus, and cut elimination for propositional logic

What is the precise connection between: strong normalization of the simply typed $\lambda$-calculus, and cut elimination for (intuitionistic) propositional logic (limited to implication) in “sequent ...
Gro-Tsen's user avatar
  • 619
1 vote
0 answers
63 views

Crafting ${NP}^{\#P}$-complete problems

Some related posts: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$? $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$ I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
Habri's user avatar
  • 11
2 votes
0 answers
42 views

Variable opening in locally-nameless representation

Although similar to a previously unanswered question, my query focuses on a different aspect of normalization. I'm trying to adjust the proof of strong normalization of STLC, given in Jeremy Avigad's ...
phdstudent's user avatar
0 votes
0 answers
16 views

Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
Tim's user avatar
  • 1
3 votes
1 answer
169 views

What’s the complexity of this decision problem with bit shifting?

I’ve been wondering about the computational complexity of a problem that involves bit shifting. Let me define some notation before I present the problem. If $\langle{b}\rangle$ is a bitstring ...
Sophie Weigle's user avatar
0 votes
1 answer
59 views

Learning positive half-lines (in $\mathbb{N}$)

The second section of these notes points explains how one might PAC learn the concept class of intervals of all positive half-lines in $\mathbb{R}$. If we restricted our attention to $\mathbb{N}$ ...
meeeeee's user avatar
  • 21
2 votes
2 answers
81 views

Learning with zero inductive bias

I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a ...
rivana's user avatar
  • 53
2 votes
0 answers
21 views

Hardness of 3-Partition with Small Target Value

In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
John's user avatar
  • 173
6 votes
0 answers
64 views

Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
gsv's user avatar
  • 421
3 votes
1 answer
344 views

Intuition on Lupanov's Upper Bound on Circuit Size

The following result, by Lupanov, is a classic in the theory of Boolean function complexity: Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
sdsdsd's user avatar
  • 133
2 votes
0 answers
38 views

Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?

I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function. I was surprised seeing that the upper bounds for time ...
rivana's user avatar
  • 53
0 votes
0 answers
16 views

What is the condition under which the estimation error increases (logarithmically) with hypothesis class size for a finite hypothesis class

In section 5.2 error decomposition (p.404) from the online book "Shai et al., Understanding Machine Learning: From Theory to Applications", the authors wrote: As we have shown, for a finite ...
Tran Khanh's user avatar
0 votes
0 answers
40 views

Computability of Time Complexity of Recursive Sets

Is every recursive set's worst-case time complexity a total recursive function?
A. P. Pille's user avatar
1 vote
1 answer
78 views

Learning arithmetic series

Let us say that an arithmetic series is a series of the form $s_t = \{0, t, 2t, \ldots\}$. For example, $s_3 = \{0, 3, 6, \ldots\}$. Now consider the concept class composed of all arithmetic series of ...
meeeeee's user avatar
  • 21
4 votes
1 answer
102 views

Lower bound for constant degree monotone arithmetic circuits

Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size $n^{10}$?
ivmihajlin's user avatar
-4 votes
2 answers
120 views

Why is it impossible to prove software to be correct?

I heard that computer programs can't be proved to be correct, only tested. Could anyone explain to a math student who knows logic and how to prove theorems in mathematics that why is this impossible? ...
student's user avatar
-1 votes
0 answers
38 views

What are the prerequisites for reading the book "Understanding machine learning: from theory to algorithms"

The book mentions "the reader is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms" I am a graduate in electronics engineering. I have ...
Sathishkumar Thirumalai's user avatar

15 30 50 per page
1
2 3 4 5
254