# All Questions

10,811 questions
Filter by
Sorted by
Tagged with
29 views

### MaxCut instance with least number of cuts

Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of cuts in its ...
120 views

### What are some algorithms where space complexity tends to be the limiting factor in practice?

Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
45 views

### Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties: The size of $\psi$ is ...
42 views

### How can I calculate nonstandard binary representations quickly?

I'm looking to convert standard unsigned binary numbers (machine integers) to each of several similar nonstandard binary representations. First representation Each digit is 1, 2, or 3. Second ...
51 views

### Best known hidden constant in complexity of AKS sorting networks

The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$. The ...
97 views

### Polynomial evaluation at all different points

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
27 views

### Hardwiring the output in a quantum circuit

In this paper, while using a diagonalization argument in Section $5$, the authors write: Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1}, M_{2},...$ which we can do because the ...
42 views

I'm unsure whether the following three equations constitute a valid instance of a reader/environment monad on the simply-typed lambda calculus, where $\alpha$ is any type (I subscript some terms with ...
48 views

### If machine learning can cover any CS problem, wouldn't it prove that P=NP? [closed]

My (naive) comprehension is that any CS problem, both P and NP, could be expressed as a set of data to expose to ML computation. It doesn't matter how much time the ML algorithm would take to learn ...
19 views

### Does an answer-set in answer-set-programming have to be a model of the program

I have found several definitions for the answer-set of a program P that go like this: An interpretation M is an answer set of a ground program P iff it is a minimal model of Pm, where Pm is the ...
36 views

### Existing implementation of “grounding for first order logic formulas”?

I am sorry if this is off-topic here. I am looking for a simple implementation of grounding a function free first order logic formula. Does anyone know of any existing implementation ?
31 views

### How to approach SAT-related reduction/proofs? (Double-SAT)

I am preparing for my exam next month and was stuck when it came to SAT reductions/proofs. Could someone help me out in understanding this question? Double-SAT = {< ϕ > | ϕ is a Boolean formula ...
14 views

### High probability bound on the difference between expected cumulative reward and cumulative reward

Consider a MDP $M$ with a finite state space $S$ and a finite action space $A$. When executing an action $a$ in state $s$, the learner receives a random reward $r$ drawn independently from some ...
46 views

### reference request: greedy algorithm for fractional interval covering

Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ...
70 views

### On solving Planar Circuit SAT

This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
59 views

### tables of reductions in literature [closed]

I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. ...
121 views

### Formal theory about explaining algorithms

There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing ...
22 views

### System of equations with infinite dimensional variable

I have a system of equations of the following $$z(n)=c+\delta\big[p_1z(n+1)+p_2z(n-1)+(1-p_1-p_2)z(n)\big]~~if~~n\geq 0$$ and $$z(n)=\delta\big[p_1z(n+1)+p_2z(n-1)+(1-p_1-p_2)z(n)\big]~~if~~n< 0$$ ...
89 views

### Is Scott's reduction sound for $\mathrm{FO}^2$ with equality?

As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...
95 views

### Does focused proof search ever have to backtrack across the choice of focus formula?

There are a lot of different "focused" sequent calculi for lots of different logics, but my understanding is that many or most of them have the following flavor. First one divides the ...
163 views
+100

### Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
129 views
+50

### Complexity of finding the most likely edge

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...
8 views

### No 13 in the sequence [migrated]

There are "n" number of box's each box we can place 0-9 numbers .. condition is that 13 is not occurred at any place in sequence.. I take n = 3; and so total possiblities is 101010 = 1000 ,...
75 views

### Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
42 views

### Problems people face with computer science professions (outside of work)

I am writing an article for a classroom project shedding light on the major issues that Computer Programmers face outside of work. I am not really looking for anything too in-depth concerning ...
23 views

### granularity of bidirectional breadth-first search

I tried posting this on stack overflow and it got no takers, decided to cross post here: One thing that I've never seen discussed about bidirectional breadth-first-search (which I'll abbreviate as ...
51 views

### 3SAT ≤L SUBSET-SUM

There's the common polynomial reduction from 3SAT to SUBSET-SUM as described here, but what about a log-space reduction from 3SAT to SUBSET-SUM? I came across this question a few days ago but still ...
27 views

### What is the best way to find circles that contain a given point (in 2D)?

Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions. ...
172 views

### How can I find the PhD thesis of C.A. Ellis?

I've searched for this article all over the web but couldn't find it. can anyone help me? Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp. Sc. University of Illinois, ...
42 views

### Sample graph dataset for testing algorithms

I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...). There are a ...
67 views

5k views

### Implications of proving NP=RP on complexity theory

Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...
2k views

### Examples of collapsing hierarchies

Are there interesting examples of "collapsing hierarchies" in computer science? The formal definition of a hierarchy here would be a class of languages/problems/objects which is ...
33 views

### What to choose Deep learning or Artificial Intelligence after learning basic Machine Learning? [closed]

I Learned basics from Machine Learning and its algorithm and I wanted to choose the on subject from deep learning and artificial neural network so I am confused which one to choose can any one guide ...
64 views

### Relation between Randomized and Distribution complexity

$DistNP$ is contained in $AvgP$ does not imply that $NP=RP$ by https://dl.acm.org/doi/10.1109/CCC.2011.34. Do we know if $NP=RP$ then $DistNP$ is contained in $AvgP$? or $PP=BPP$ then $DistNP$ is ...
261 views

### When was co-NP introduced for the first time?

My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
185 views

### Who introduced the notion of Non-Deterministic Polynomial time?

In his 1972 paper, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one? Edit Edmonds mentions the idea ...
47 views

### The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
81 views

### Category theory lambda cube?

If simply typed lambda calculus corresponds to cartesian closed categories, what types of categories do other calculi in the lambda cube correspond to? https://en.m.wikipedia.org/wiki/Lambda_cube
97 views

### Normal forms for counting quantifiers?

In the paper by [Erich Grädel and Martin Otto], the authors state that any formula in First Order Logic with two variables with counting quantifiers can be reduced to a formula of the form  \forall ...
32 views

### Applying hypothesis with unknown variables [closed]

0 I'm trying to prove the following lemma about functions on natural numbers ...
150 views

### Categorical equivalent of higher order logic

From Simply typed lambda calculus and higher order logic, I get the impression that HOL is STLC + equality + equality axioms. I was wondering if there is a particular kind of category modelling this.
52 views

### Reference request on using Kolmogorov complexity to measure the simplicity of models

Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of ...
59 views

86 views

### What's the constant coefficient of the Coppersmith-Winograd algorithm?

Every source I can find just says "too big to be practical."
62 views

### Describing circuits with bits

I'm currently reading the book Computational complexity from Arora and Barak. In chapter 6 (page 114) about Boolean functions the authors are proving the Karp-Lipton theorem, in the proof they use the ...