Stack Exchange Network

Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Loading…
  1. 0
  2. +0
    • Tour Start here for a quick overview of the site
    • Help Center Detailed answers to any questions you might have
    • Meta Discuss the workings and policies of this site
    • About Us Learn more about Stack Overflow the company
    • Business Learn more about hiring developers or posting ads with us
  3. Log in Sign up
  4. current community

    • Theoretical Computer Science
      help chat
    • Theoretical Computer Science Meta

    your communities

    Sign up or log in to customize your list.

    more stack exchange communities

    company blog
Theoretical Computer Science
  1. Home
    1. Questions
    2. Tags
    3. Users
    4. Unanswered
    5. Jobs
Profile Activity
Meta user
Network profile
Karolina Sołtys

Reputation

1,344
  • 1.3k
  • 1.3k
  • 1.2k
  • 2018
  • 2019
  • 2020
  • 2021

Top tag

cc.complexity-theory

Next privilege

2,000 Rep.
Edit questions and answers

Badges

8
13

Newest

 Yearling

Next badge

0/1
Custodian

Impact

~13k
people reached
0 posts edited
0 helpful flags
64 votes cast
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

64 Bookmarks

Votes Activity Newest Views Added
44
votes
5
answers
1k
views

Casual tours around proofs

soft-question big-list
Nov 11 '11 at 8:00 Kris 143
20
votes
1
answer
567
views

FPT vs W[P] - Parameterized Complexity

cc.complexity-theory parameterized-complexity fixed-parameter-tractable
Apr 8 '15 at 15:34 Huck Bennett 4,422
24
votes
19
answers
3k
views

What tools do you use to give presentations?

soft-question research-practice writing
May 10 at 19:38 Denis 6,695
26
votes
5
answers
2k
views

Long-lasting errors in computer science

soft-question big-list
Aug 21 '11 at 8:26 Jukka Suomela 11.1k
134
votes
29
answers
21k
views

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate
Aug 15 at 23:45 Mark S 802
33
votes
3
answers
939
views

An Anthology of Complexity Assumptions

cc.complexity-theory complexity-classes big-list complexity-assumptions
Sep 1 '15 at 18:22 Community♦ 1
10
votes
2
answers
432
views

Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

cc.complexity-theory approximation-algorithms approximation-hardness
Mar 30 '11 at 6:17 Daniel Marx 1,948
27
votes
4
answers
1k
views

Compendium of the Best Approximation and Hardness Results for NP optimization problems

ds.algorithms reference-request approximation-algorithms approximation-hardness
Aug 25 '11 at 16:14 Randomizer 761
16
votes
2
answers
920
views

Collatz Conjecture & Grammars / Automata

fl.formal-languages nt.number-theory halting-problem
Nov 27 '13 at 2:16 Community♦ 1
54
votes
2
answers
3k
views

Can one amplify P=NP beyond P=PH?

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy
May 18 '17 at 12:42 András Salamon 18.4k
23
votes
1
answer
870
views

Is there any justification to believe that $NL\neq L$?

cc.complexity-theory reference-request complexity-classes space-bounded
Mar 11 '11 at 22:56 Ryan Williams 25.7k
12
votes
1
answer
665
views

Improved lower bound on monotone circuit complexity of perfect matching?

cc.complexity-theory circuit-complexity matching
Jan 12 '11 at 16:01 V Vinay 3,783
15
votes
2
answers
968
views

Barriers and Monotone Circuit Complexity

cc.complexity-theory circuit-complexity barriers natural-proofs
Dec 18 '10 at 15:07 dick lipton 451
25
votes
3
answers
990
views

Reverse Graph Spectra Problem?

ds.algorithms graph-theory graph-algorithms spectral-graph-theory
Feb 13 '16 at 5:13 Jeffrey Shallit 6,818
3
votes
0
answers
240
views

Is there any research on the notion of weak isolation?

cc.complexity-theory randomness
Dec 11 '10 at 13:23 Hsien-Chih Chang 張顯之 7,438
26
votes
4
answers
943
views

What's the “smallest” complexity class for which a superlinear circuit bound is known?

cc.complexity-theory circuit-complexity
Oct 4 '17 at 2:22 Dmytro Taranovsky 2,092
21
votes
6
answers
1k
views

References on Circuit Lower Bounds

cc.complexity-theory lower-bounds circuit-complexity
Apr 15 '11 at 13:18 M.S. Dousti 16.1k
51
votes
4
answers
3k
views

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

cc.complexity-theory space-bounded big-picture
Dec 2 '10 at 13:54 Michael Blondin 2,492
12
votes
1
answer
275
views

Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

cc.complexity-theory circuit-complexity polynomials algebraic-complexity
Nov 30 '10 at 14:13 Joshua Grochow 34.1k
29
votes
7
answers
2k
views

Proving lower bounds by proving upper bounds

cc.complexity-theory lower-bounds
Dec 8 '10 at 5:15 Community♦ 1
30
votes
3
answers
3k
views

coNP certificate for Graph Isomorphism

cc.complexity-theory graph-isomorphism
Jan 5 '11 at 14:38 Francesco Cris 9
42
votes
4
answers
3k
views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

computability lo.logic proofs
Jul 18 '11 at 18:58 Community♦ 1
15
votes
0
answers
1k
views

Can a Penrose tile cellular automaton be Turing-complete?

computability machine-models cellular-automata
Nov 11 '10 at 22:18 Community♦ 1
6
votes
2
answers
378
views

PCPs with imperfect completeness

cc.complexity-theory reductions pcp
Nov 8 '10 at 20:49 Ramprasad 2,427
29
votes
2
answers
911
views

Polynomial method for complexity results

cc.complexity-theory reference-request co.combinatorics polynomials
Nov 11 '10 at 13:20 Dana Moshkovitz 10.8k
65
votes
11
answers
5k
views

What are good references to understanding the proof of the PCP theorem?

cc.complexity-theory reference-request pcp
Sep 21 '16 at 19:42 Sasho Nikolov 17.8k
9
votes
2
answers
733
views

Quantum PCP and hardness of simulating of Hamiltonians

cc.complexity-theory quantum-computing approximation-hardness pcp physics
Oct 13 '13 at 0:46 Community♦ 1
22
votes
4
answers
1k
views

DNA-algorithms and NP-completeness

cc.complexity-theory np-hardness natural-computing tsp
Nov 7 '10 at 5:41 Kaveh 21k
33
votes
3
answers
2k
views

complexity of greatest common divisor (gcd)

cc.complexity-theory reference-request complexity-classes nt.number-theory
Jan 5 '15 at 16:24 SamiD 2,267
23
votes
4
answers
1k
views

Social choice, arrow's theorem and open problems ?

co.combinatorics gt.game-theory boolean-functions social-sciences
Nov 30 '10 at 6:49 H. Reiju Mihara 71
1
2 3 Next
Theoretical Computer Science
  • Tour
  • Help
  • Chat
  • Contact
  • Feedback
  • Mobile
Company
  • Stack Overflow
  • For Teams
  • Advertise With Us
  • Hire a Developer
  • Developer Jobs
  • About
  • Press
  • Legal
  • Privacy Policy
  • Terms of Service
Stack Exchange
Network
  • Technology
  • Life / Arts
  • Culture / Recreation
  • Science
  • Other
  • Stack Overflow
  • Server Fault
  • Super User
  • Web Applications
  • Ask Ubuntu
  • Webmasters
  • Game Development
  • TeX - LaTeX
  • Software Engineering
  • Unix & Linux
  • Ask Different (Apple)
  • WordPress Development
  • Geographic Information Systems
  • Electrical Engineering
  • Android Enthusiasts
  • Information Security
  • Database Administrators
  • Drupal Answers
  • SharePoint
  • User Experience
  • Mathematica
  • Salesforce
  • ExpressionEngine® Answers
  • Stack Overflow em Português
  • Blender
  • Network Engineering
  • Cryptography
  • Code Review
  • Magento
  • Software Recommendations
  • Signal Processing
  • Emacs
  • Raspberry Pi
  • Stack Overflow на русском
  • Code Golf
  • Stack Overflow en español
  • Ethereum
  • Data Science
  • Arduino
  • Bitcoin
  • Software Quality Assurance & Testing
  • Sound Design
  • Windows Phone
  • more (28)
  • Photography
  • Science Fiction & Fantasy
  • Graphic Design
  • Movies & TV
  • Music: Practice & Theory
  • Worldbuilding
  • Video Production
  • Seasoned Advice (cooking)
  • Home Improvement
  • Personal Finance & Money
  • Academia
  • Law
  • Physical Fitness
  • Gardening & Landscaping
  • Parenting
  • more (10)
  • English Language & Usage
  • Skeptics
  • Mi Yodeya (Judaism)
  • Travel
  • Christianity
  • English Language Learners
  • Japanese Language
  • Chinese Language
  • French Language
  • German Language
  • Biblical Hermeneutics
  • History
  • Spanish Language
  • Islam
  • Русский язык
  • Russian Language
  • Arqade (gaming)
  • Bicycles
  • Role-playing Games
  • Anime & Manga
  • Puzzling
  • Motor Vehicle Maintenance & Repair
  • Board & Card Games
  • Bricks
  • Homebrewing
  • Martial Arts
  • The Great Outdoors
  • Poker
  • Chess
  • Sports
  • more (16)
  • MathOverflow
  • Mathematics
  • Cross Validated (stats)
  • Theoretical Computer Science
  • Physics
  • Chemistry
  • Biology
  • Computer Science
  • Philosophy
  • Linguistics
  • Psychology & Neuroscience
  • Computational Science
  • more (10)
  • Meta Stack Exchange
  • Stack Apps
  • API
  • Data
  • Blog
  • Facebook
  • Twitter
  • LinkedIn
  • Instagram

site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2021.2.25.38657