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
Erel Segal-Halevi

Reputation

1,576
  • 1.6k
  • 1.3k
  • 955
  • 2018
  • 2019
  • 2020
  • 2021

Top tag

ds.algorithms

Next privilege

2,000 Rep.
Edit questions and answers

Badges

7
18

Newest

 Yearling

Next badge

0/1
Custodian

Impact

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

18 Bookmarks

Votes Activity Newest Views Added
471
votes
70
answers
169k
views

What papers should everyone read?

big-list soft-question
Feb 15 '20 at 16:45 gadmm 55
116
votes
18
answers
8k
views

Examples of the price of abstraction?

ds.algorithms reference-request big-list lower-bounds
Aug 23 at 22:20 sdcvvc 1,241
48
votes
8
answers
5k
views

Are there non-constructive algorithm existence proofs?

ds.algorithms soft-question lo.logic proofs
Aug 11 '12 at 20:01 Community♦ 1
28
votes
4
answers
1k
views

Maximal classes for which largest independent set can be found in polynomial time?

ds.algorithms graph-theory co.combinatorics graph-classes
Oct 1 '14 at 2:17 Community♦ 1
24
votes
5
answers
3k
views

Approximation algorithms for Maximum Independent Set on special classes of graphs

ds.algorithms graph-theory graph-algorithms approximation-algorithms
Jan 26 '14 at 18:56 Erel Segal-Halevi 1,576
24
votes
3
answers
2k
views

Hardness of approximation - additive error

cc.complexity-theory complexity-classes np-hardness approximation-hardness
Nov 24 '10 at 14:31 Tsuyoshi Ito 16.1k
23
votes
1
answer
3k
views

Computational complexity of the 3-partition problem with distinct numbers

cc.complexity-theory np-hardness
Aug 30 '10 at 0:35 Community♦ 1
23
votes
5
answers
2k
views

Packing rectangles into convex polygons but without rotations

reference-request np-hardness cg.comp-geom optimization packing
Mar 21 '11 at 19:36 Community♦ 1
18
votes
2
answers
2k
views

Algorithms for set packing

ds.algorithms
Sep 24 '16 at 10:25 Community♦ 1
17
votes
3
answers
486
views

Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

ds.algorithms approximation-algorithms cg.comp-geom graph-colouring online-algorithms
Jan 7 '19 at 8:34 Glorfindel 205
15
votes
1
answer
426
views

Information complexity of query algorithms?

it.information-theory communication-complexity query-complexity
Apr 15 '15 at 9:05 TCS-user-12 99
11
votes
2
answers
2k
views

Cover a Concave Polygon with a minimum number of rectangles

co.combinatorics cg.comp-geom
Dec 1 '12 at 5:56 Community♦ 1
11
votes
3
answers
2k
views

Extension to the Stable Marriage Problem ?

ds.algorithms graph-theory matching
Oct 4 '10 at 2:00 Community♦ 1
9
votes
1
answer
750
views

NP-Hardness of a special case of orthogonal packing problem

cc.complexity-theory reference-request np-hardness packing
Dec 17 '10 at 16:06 Oleksandr Bondarenko 4,165
9
votes
1
answer
225
views

Counting the number of thick regions which overlap a square

cg.comp-geom
Apr 16 '12 at 20:37 Joe 1,307
8
votes
1
answer
664
views

Is that particular case of the “minimum weight solution to linear equations” still NP-complete?

cc.complexity-theory np-hardness cg.comp-geom application-of-theory
Dec 16 '10 at 5:09 Tsuyoshi Ito 16.1k
7
votes
0
answers
647
views

Hardness of Approximation results for Special Set Packing Problem Wanted

cc.complexity-theory approximation-algorithms approximation-hardness set-cover packing
Nov 24 '12 at 7:10 Community♦ 1
2
votes
1
answer
188
views

Solving linear program with 1 quadratic constraint complexity

np-hardness optimization linear-programming
Sep 18 '17 at 16:42 karmanaut 953
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.1.18.38333