Questions tagged [soft-question]

A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16
votes
0answers
804 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
14
votes
0answers
429 views

Manuel Blum's supervisory style

Manuel Blum is a well-known theoretical computer scientist and a Turing award winner. But more interestingly, he has the highest number of students who have gone on to win a Turing award (Leonard ...
14
votes
0answers
282 views

First use of sans serif for complexity classes

(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...) It seems that it has become popular in recent years to ...
13
votes
0answers
369 views

What percentage of SODA papers are galactic algorithms?

Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
12
votes
0answers
474 views

Looking for a quotation by Edsger Dijkstra

In one of his papers Edgser Dijkstra makes a statement like: "What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
10
votes
0answers
212 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
8
votes
0answers
140 views

How to succeed in remote TCS research as undergraduate

I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
8
votes
0answers
648 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
7
votes
0answers
178 views

Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
7
votes
0answers
225 views

Low barrier to entry Computational Complexity problems

I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to ...
7
votes
0answers
308 views

Awards, grants and fellowships for PhD students in TCS

I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for? ...
7
votes
0answers
542 views

Does a depth knowledge on theory of computation helps to be a better practitioner

I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would ...
6
votes
0answers
316 views

What is the current status of Acta Informatica?

Almost everybody knows the journal Acta Informatica. Some really important publications appeared there over the years. Upon looking on the website of the journal I noticed the following: Number of ...
6
votes
0answers
423 views

What makes for a good paper abstract?

I am writing a paper for a TCS conference and wondering what the community's opinion is on how abstracts in TCS should be written, good practices, or rules of thumb. I thought that I had read enough ...
6
votes
0answers
914 views

What should I do to switch from math department to cs to research tcs topics?

This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first. I'm now a math student of master ...
6
votes
0answers
292 views

Formula in common: How to search for same/similar equations in other knowledge domains?

In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in http://www.cs.princeton.edu/~rs/talks/AofA2AC....
6
votes
0answers
422 views

What is the origin and meaning of the phrase "Lambda the ultimate?"

I've been messing around with functional programming languages for a few years, and I keep encountering this phrase. I understand what lambda means, the idea of an anonymous function is both simple ...
5
votes
0answers
130 views

Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
5
votes
0answers
169 views

What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
5
votes
0answers
179 views

Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
5
votes
0answers
136 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
5
votes
0answers
236 views

Being a theoretician at a business university?

I'm currently on the job market and I've seen some open faculty positions in computer science at a business university (which is quite reputable among its kind). While the job opening doesn't ...
5
votes
0answers
120 views

conceptual tools for illustrating types of computation?

From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc. The common theme is ...
5
votes
1answer
157 views

Interesting programs on small machines

I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1 ...
4
votes
0answers
82 views

Simple randomized priority queue matching the Fibonacci heap time bounds?

Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.). Many classical worst-case ...
4
votes
0answers
198 views

What kind of research can be considered publishable for undergraduate or graduate students (MSc level)

I'am currently doing a non-research Dipl.Eng (Engineering Diploma in French school system equivalent to MSc) in Computer Science. The courses I am currently taking are software oriented, there's an ...
4
votes
0answers
151 views

The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
4
votes
0answers
97 views

Status of the Junta Problem (soft question)

Does the learning theory community in general believe that juntas can be learned in polynomial time? The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
4
votes
0answers
95 views

Naming an algorithm after a copyrighted object

In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
4
votes
0answers
124 views

major applied focuses of different proof assistants

Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences ...
3
votes
0answers
113 views

Metrics for modelling convergence in the lambda-calculus

I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure ...
3
votes
0answers
169 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
3
votes
0answers
549 views

Book Recommendations for a General Introduction to (Theoretical) Computer Science

After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to ...
3
votes
0answers
101 views

Notion of "total work" of a problem?

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
2
votes
0answers
161 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
2
votes
0answers
155 views

Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...
2
votes
0answers
281 views

Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
2
votes
0answers
54 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
2
votes
0answers
238 views

Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

How common is it to place articles on arXiv or similar sites before publishing in a peer-reviewed journal? I'm trying to get a feel for what my chances are, of publishing in a journal if I put an ...
1
vote
0answers
19 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
1
vote
0answers
258 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
1
vote
0answers
78 views

"conservative approximate Set Cover"?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$). The task is to approximately cover $L$ with translated, rotated and flipped ...
1
vote
0answers
1k views

How to find interesting algorithms to implement?

I am not a researcher in algorithms (I am a college freshman). I would like to implement an interesting recent algorithm from a data structure/algorithms paper. How can find a good algorithms paper ...
0
votes
0answers
130 views

I think I may have discovered a new algorithm for a common problem. Now what?

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
0
votes
0answers
303 views

What is the difference between a TCS PhD thesis and Computer Science experimental PhD thesis?

I'm doing my PhD in computer science, namely theoretical computer science and currently waiting for my VIVA. I think one of my examiner is an experimental person, how can I convince her that my work ...
0
votes
0answers
266 views

introduction to spectral geometry

In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The ...
0
votes
0answers
395 views

Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic. What's the reason for this? Are there any related problems, ...
-1
votes
0answers
76 views

Open Problems in Quantum Complexity Theory (2021)

What are some open problems in quantum computing or complexity theory where a novice researcher could reasonably hope to make contributions with a few months of steady effort? I know this question has ...