All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
34 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
25 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
7 votes
1 answer
317 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
  • 599
5 votes
1 answer
130 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
75 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
65 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
47 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
113 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
39 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
402 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
53 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
-1 votes
0 answers
44 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
42 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
0 votes
0 answers
38 views

How the correctness of this construction can be proved? [closed]

We are using Myhill-Nerode Theorem algorithm and we want to prove that this algorithm gives us the minimized DFA. So let $B$ be the minimized DFA obtained by applying the algorithm to the DFA $A$. We ...
likeAvirgin's user avatar
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
122 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
63 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
58 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
97 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
23 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
427 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
  • 599
1 vote
1 answer
97 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
49 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
38 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
3 votes
1 answer
133 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
  • 599
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
15 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
2 votes
1 answer
168 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
56 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
77 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
62 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
100 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
116 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
16 votes
0 answers
1k views

Are theoretical computer science conferences losing touch with reality?

Anonymous account for obvious reasons. I am a researcher in TCS. I have several publications in SODA/STOC/FOCS. I've recently been so disgruntled with the way these conferences are run, and wanted to ...
DisgruntledTCSResearcher's user avatar
0 votes
1 answer
30 views

Why is the estimation error smaller in Structural Risk Minimization

On p.87 in this online Understanding Machine Learning book, the authors wrote: Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, $L_S(h)$, but ...
Tran Khanh's user avatar
1 vote
0 answers
47 views

Relation Between Different Definitions of Information Distance

I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
Ravi Deedwania's user avatar
0 votes
0 answers
97 views

Assume `P != NP`, does it imply that one-way functions exist?

I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
Zazaeil's user avatar
  • 212
4 votes
1 answer
105 views

High-dimensional expanders through the lens of algebraic topology

High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
p-adict's user avatar
  • 43
4 votes
2 answers
519 views

Do we currently know a polynomial-size Frege proof for Tseitin formulas?

There's a vast literature about super-polynomial lower bounds on proof lengths of Tseitin formulas in bounded-depth Frege systems, but what I'm curious about is: what if we don't restrict the depth of ...
Soha's user avatar
  • 145
1 vote
0 answers
39 views

Why the measure of information complexities for passive and active learning are increasing in research communities?

I am a PhD student working on the theory of active learning. Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
Ayoubayjx's user avatar
  • 122
10 votes
0 answers
203 views

Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?

I am lost in a maze of twisty little type theories, all different. There are a number of works (textbooks and papers) that discuss pure type theories, and specifically the ones constituting the ...
Gro-Tsen's user avatar
  • 599

15 30 50 per page
1
2 3 4 5
254