Questions tagged [software]
Questions about Software/Programs/Applications used by TCS researchers
34
questions
21
votes
10answers
3k views
#SAT Solver download
Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an ...
2
votes
1answer
112 views
Are there any implementations of a graph crossing algorithm?
This is much more focused version of this question:
Are there good implementations for easy subclasses of NP-hard graph problems
Computing the graph-crossing number $cr(G)$ for a simple graph is ...
-2
votes
1answer
44 views
Differences in the requirements for different bit architectures [closed]
I've noticed that software that exists as a 32-bit-version and a 64-bit-version often has higher system requirements if you want to install the 64-bit version.
One example is Windows 10
The 32-bit ...
21
votes
5answers
2k views
Program for computing Tree decomposition of a graph
Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
2
votes
0answers
60 views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
1
vote
1answer
168 views
Practical approaches to solving whether programs will halt
What kinds of systems are available that accept a certain program $P$ and attempts to figure out "the program does terminate" or "the program does not terminate" and output a proof of one or the other?...
4
votes
1answer
176 views
Have fixed parameter integer program algorithms ever been implemented for research use?
Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
14
votes
5answers
2k views
Best book on Simplex Method implementation?
I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
3
votes
0answers
183 views
Min dominating set software
I need a fast min-dominating-set code for some complexity lower bounds research I am doing.
I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something ...
3
votes
0answers
85 views
Software that generates and solves a Lasserre hierarchy
Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
11
votes
2answers
1k views
Enumerate all solutions of a SAT problem
All the #SAT solvers I know, e.g RelSat, C2D, only return the number of satisfiable instances. But I want to know each of those instances?
Is there such a #SAT solver or how I should modify an ...
3
votes
1answer
548 views
Is there a tool for finding Nash equilibria in parametric games?
There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix.
Such tools are Game Theory Explorer and Gambit.
However, as ...
21
votes
9answers
12k views
What is the recommended software for drawing data structures such as graphs and trees?
When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
8
votes
0answers
336 views
Are there any implementations of Cook-Levin?
Does anyone know if there is an implementation of Cook-Levin?
A program that gets an input like the following:
$M$: the code of a machine model/simple program in a programming language like C,
$\vec{...
-1
votes
1answer
3k views
Program optimization - 90/10 law
I found this "law" somewhere on Wikipedia:
In software engineering, it is often a better approximation that 90% of the execution time of a computer program is spent executing 10% of the code (known ...
3
votes
1answer
281 views
Approximate-#SAT solver
I am looking for a solver that computes an approximation to #SAT. In other words, given a formula $\phi(x)$ in CNF, approximately count the number of satisfying assignments to $\phi$. I'm interested ...
36
votes
8answers
2k views
Collaborative tools for dummies/professors
Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth.
They realize they can open for ...
20
votes
5answers
2k views
Version control for collaboration (with word-level diffs)?
Most papers are now written collaboratively, and collaborators are often located in different places. I have always used version control systems for my documents and code, and have also found version ...
7
votes
2answers
334 views
Is there software for graph product calculation and visualization?
I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.
More specifically, I work with labeled, directed multigraphs, and would ...
12
votes
6answers
2k views
Proof assistant for writing mathematics
I'd like to write mathematical proofs using some proof assistant. Everything will be written using first order logic (with equality) and natural deduction. The background is set theory (ZF). For ...
-1
votes
2answers
280 views
Will we be able to use the current software in quantum computers? [closed]
I'm not sure if this should go here, so my apologies. The fact is that lately I have heard a lot about quantum computers and that they are not that far away. As it is a totally new technology, which ...
15
votes
5answers
455 views
Software package for decomposing quantum circuits
Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?
9
votes
1answer
1k views
Computing volume of high-dimensional convex polyhedra
I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-...
0
votes
0answers
163 views
Tool for managing scientific papers [duplicate]
Possible Duplicate:
Do you use any article organizers?
As part of my Ph.D. studies I need to create an overview of recently (since 2000) published papers with impact on my study field.
Creating ...
3
votes
0answers
239 views
0
votes
1answer
1k views
Generating a language from a given grammar
So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there ...
28
votes
1answer
827 views
Is there a reasonable automated proof system for TCS theorems?
Suppose I wanted to formalize Turing's proof regarding the halting problem so that a machine could check it. Some of the well-known automated theorem proving systems include Mizar, Coq, and HOL4. I ...
20
votes
6answers
3k views
Network / Social network analysis visualization tools?
I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
3
votes
1answer
329 views
Are there good implementations for easy subclasses of NP-hard graph problems
Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
5
votes
2answers
469 views
Software for Graph Analysis
I have some graph-data which I would like to analyze. If the software could automatically determine some characteristics (Is the graph planar, clique number or any other graph property) it would be ...
7
votes
2answers
453 views
A System for Visualizing Bibliography Information
I'm looking for a software for visualizing main trends in some field.
Specifically, I want it to build a graph of the field with vertexes representing papers and edges representing how close papers ...
6
votes
2answers
280 views
Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)
In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy ...
8
votes
5answers
6k views
What are theoretically sound programming languages for graph problems?
There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?
8
votes
1answer
440 views
Tool for translating PDAs to CFGs
We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
