All Questions
12,683
questions
1
vote
0
answers
18
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 ...
- 131
1
vote
0
answers
41
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 ...
-1
votes
0
answers
20
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 ...
- 283
5
votes
1
answer
177
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 ...
- 16.8k
54
votes
7
answers
4k
views
Good examples for how to write well in TCS
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 ...
- 36.9k
3
votes
1
answer
302
views
Online TCS Seminars
I want to have a list of online seminars that holds now.
So far I know only about TCS+(https://sites.google.com/site/plustcs/) seminars.
I would like to ask if there are other TCS seminars.
- 36.9k
2
votes
1
answer
119
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 ...
- 2,119
0
votes
2
answers
57
views
Representing/Modelling fields and methods in the context of programming as automata
I am trying to represent/model fields and methods in the context of programming as automata. For instance, let's say that I have field1 with state equal to 2, ...
CommunityBot
- 1
-1
votes
0
answers
71
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 ...
0
votes
1
answer
88
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 ...
- 10.3k
5
votes
2
answers
350
views
Error in Robson's proof about separting 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})$.
...
- 681
6
votes
3
answers
419
views
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Problem:
Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
- 5,840
2
votes
0
answers
54
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 ...
- 1,078
4
votes
0
answers
107
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 ...
- 2,086
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$...
0
votes
1
answer
47
views
How to calculate processor throughput boundary in CSAPP?
In Chapter 5.7 of CSAPP, author list out the throughput boundary of Intel Core i7 Haswell while executing the operation Integer addition and multiplication, floating points addition and multiplication....
- 1
2
votes
0
answers
48
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 ...
- 33
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\...
- 3,416
-2
votes
1
answer
57
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 ...
- 10.3k
-1
votes
0
answers
43
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 ...
0
votes
1
answer
57
views
Detecting Erroneous Corrections
A block code $C$, with minimum distance $d$ can be used to:
Detect $d - 1$ errors
Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors
However, the above usually assumes that the number of errors that are ...
CommunityBot
- 1
-2
votes
0
answers
41
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 ...
- 1
1
vote
1
answer
118
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 ...
- 464
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 ...
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,...
- 122
-1
votes
0
answers
62
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 "...
- 53
-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 ...
- 99
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 ...
- 10.3k
1
vote
1
answer
237
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
CommunityBot
- 1
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 $...
- 136
2
votes
2
answers
418
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 ...
- 577
0
votes
1
answer
145
views
SAT to k-in-3-SAT reduction
Given a 3-SAT clause. Is there a way to convert 3-SAT to k-in-3-SAT such that:
The number of new variables introduced are less than the number of clauses (without adding dummy clauses etc.)?
The ...
- 549
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 ...
- 197
5
votes
1
answer
296
views
Problems complete for non-deterministic PSPACE
Savitch's theorem, i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE.
Using the idea of Savitch, Sipser proves in his lectures that TQBF is PSPACE-complete.
What ...
- 5,840
2
votes
1
answer
167
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 ...
- 11.7k
3
votes
2
answers
246
views
Where should I apply for MS in CS if I want to get admitted for Phd in TCS
I'm currently finishing my bachelor's degree of Computer Science and I'm really interested in Computational Complexity Theory and Analysis and design of Algorithms. As far as I know, if I do not have ...
- 1,868
-1
votes
0
answers
48
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 ...
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?
- 53
1
vote
0
answers
61
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 ...
- 11
0
votes
1
answer
55
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}$ ...
- 10.3k
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 ...
- 121
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? ...
- 1
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 ...
- 2,070
1
vote
3
answers
88
views
Stable/Robust Traveling Salesman Approximation Methods
I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x_1, ..., x_n$ and the set $G^* = G \cup x_{n+1}$, where $x_i$ are points in $R^d$....
- 9,595
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 ...
- 173
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 ...
- 10.3k
6
votes
0
answers
61
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, ...
- 421
3
votes
1
answer
343
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{ ...
- 632
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 ...
- 53
2
votes
2
answers
277
views
How to prove `(∀(M : Monad). ∀a. a → M a) ≅ 𝟙`
Just like the title says, how to prove that equation? The equation basically says that there is only one function a -> M a parametric in both ...
CommunityBot
- 1