|
|
Venues (Conferences, Journals, ...)
|
|
GrowBag graphs for keyword ? (Num. hits/coverage)
Group by:
The graphs summarize 1702 occurrences of 848 keywords
|
|
|
Results
Found 4049 publication records. Showing 4049 according to the selection in the facets
Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
90 | Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
Impossibility Results on Weakly Black-Box Hardness Amplification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FCT ![In: Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, pp. 400-411, 2007, Springer, 978-3-540-74239-5. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
75 | Sounaka Mishra, Kripasindhu Sikdar |
On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IFIP TCS ![In: Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference IFIP TCS 2000, Sendai, Japan, August 17-19, 2000, Proceedings, pp. 186-199, 2000, Springer, 3-540-67823-9. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
NP-optimization problems, Minimaximal and maximinimal NP-optimization problems, L-reduction, Approximation algorithms, Hardness of approximation, APX-hardness |
68 | Ronen Shaltiel, Emanuele Viola |
Hardness amplification proofs require majority. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 589-598, 2008, ACM, 978-1-60558-047-0. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
amplification, natural proofs, black-box, hardness, average-case complexity, constant-depth circuits, majority |
68 | Julia Chuzhoy, Sanjeev Khanna |
Hardness of cut problems in directed graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 527-536, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
directed multicut, hardness of approximation, sparsest cut |
61 | Alexander Healy, Salil P. Vadhan, Emanuele Viola |
Using nondeterminism to amplify hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 192-201, 2004, ACM, 1-58113-852-0. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
noise stability, pseudorandom generators for space-bounded computation, average-case complexity, hardness amplification |
57 | Vincent Conitzer, Tuomas Sandholm, Jérôme Lang |
When are elections with few candidates hard to manipulate?. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 54(3), pp. 14, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
hardness of manipulation, voting, Computational social choice |
54 | Bernhard Fuchs |
On the Hardness of Range Assignment Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CIAC ![In: Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, pp. 127-138, 2006, Springer, 3-540-34375-X. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
54 | Ronen Shaltiel, Christopher Umans |
Low-end uniform hardness vs. randomness tradeoffs for AM. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 430-439, 2007, ACM, 978-1-59593-631-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
hardness vs. randomness tradeoff, hitting-set generator, derandomization, Arthur-Merlin games |
54 | Ashkan Aazami, Michael D. Stilp |
Approximation Algorithms and Hardness for Domination with Propagation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, pp. 1-15, 2007, Springer, 978-3-540-74207-4. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS |
54 | Joseph Cheriyan, Mohammad R. Salavatipour |
Hardness and Approximation Results for Packing Steiner Trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithmica ![In: Algorithmica 45(1), pp. 21-43, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
Approximation algorithms, Steiner trees, Hardness of approximation, Packing problems |
47 | Juan Arturo Herrera Ortiz, Carlos Oliver-Morales, Katya Rodríguez-Vázquez |
Amount and type of information: a GA-hardness taxonomy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
GECCO ![In: Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, USA, July 7-11, 2010, pp. 835-836, 2010, ACM, 978-1-4503-0072-8. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
evolutionary algorithms, problem difficulty |
47 | Magnus Johnsson, Christian Balkenius |
Recognizing texture and hardness by touch. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IROS ![In: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, September 22-26, 2008, Acropolis Convention Center, Nice, France, pp. 482-487, 2008, IEEE, 978-1-4244-2057-5. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
47 | Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee |
Optimal Cryptographic Hardness of Learning Monotone Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP (1) ![In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pp. 36-47, 2008, Springer, 978-3-540-70574-1. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
47 | Lin Xu, Holger H. Hoos, Kevin Leyton-Brown |
Hierarchical Hardness Models for SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CP ![In: Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, pp. 696-711, 2007, Springer, 978-3-540-74969-1. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
47 | Neha Rungta, Eric G. Mercer |
Hardness for Explicit State Software Model Checking Benchmarks. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SEFM ![In: Fifth IEEE International Conference on Software Engineering and Formal Methods (SEFM 2007), 10-14 September 2007, London, England, UK, pp. 247-256, 2007, IEEE Computer Society, 978-0-7695-2884-7. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
47 | Chi-Jen Lu |
On the Complexity of Parallel Hardness Amplification for One-Way Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TCC ![In: Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, pp. 462-481, 2006, Springer, 3-540-32731-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
47 | Adam R. Klivans, Alexander A. Sherstov |
Cryptographic Hardness for Learning Intersections of Halfspaces. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 553-562, 2006, IEEE Computer Society, 0-7695-2720-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
47 | Asa Packer |
NP - Hardness of Largest Contained and Smallest Containing Simplices for V- and H-Polytopes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Discret. Comput. Geom. ![In: Discret. Comput. Geom. 28(3), pp. 349-377, 2002. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
47 | Guohua Jin, Luay Nakhleh, Sagi Snir, Tamir Tuller |
Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEEE ACM Trans. Comput. Biol. Bioinform. ![In: IEEE ACM Trans. Comput. Biol. Bioinform. 6(3), pp. 495-505, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
hardness and approximation, phylogenetic networks, Maximum parsimony, horizontal gene transfer |
47 | Kim Thang Nguyen |
-Hardness of Pure Nash Equilibrium in Scheduling and Connection Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SOFSEM ![In: SOFSEM 2009: Theory and Practice of Computer Science, 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 24-30, 2009. Proceedings, pp. 413-424, 2009, Springer, 978-3-540-95890-1. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
Nash equilibrium, hardness |
47 | Venkatesan Guruswami, Sanjeev Khanna |
On the Hardness of 4-Coloring a 3-Colorable Graph. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 188-197, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Graph Coloring, Hardness of approximation, PCP |
43 | Subhash Khot, Ashok Kumar Ponnuswami |
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP (1) ![In: Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, pp. 226-237, 2006, Springer, 3-540-35904-4. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
43 | Joshua Buresh-Oppenheim, Rahul Santhanam |
Making Hard Problems Harder. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pp. 73-87, 2006, IEEE Computer Society, 0-7695-2596-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
43 | Subhash Khot |
On the Unique Games Conjecture. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pp. 3, 2005, IEEE Computer Society, 0-7695-2468-0. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
43 | Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi |
Learnability and Automatizability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pp. 621-630, 2004, IEEE Computer Society, 0-7695-2228-9. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
43 | Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Generators without the XOR Lemma (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 4, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
polynomial reconstruct ion, Pseudorandom generators, extractors, list-decoding |
43 | Ronen Shaltiel, Christopher Umans |
Simple extractors for all min-entropies and a new pseudorandom generator. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 52(2), pp. 172-216, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
Hardness versus randomness, pseudorandom generator, randomness extractor |
43 | Venkatesan Guruswami |
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithmica ![In: Algorithmica 38(3), pp. 451-469, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
Set splitting, Hardness of approximations, PCP, Gadgets |
40 | Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
On the Complexity of Hardness Amplification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEEE Trans. Inf. Theory ![In: IEEE Trans. Inf. Theory 54(10), pp. 4575-4586, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
40 | Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz 0002 |
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 11-20, 2008, ACM, 978-1-60558-047-0. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
linear and semidefinite programming, metric labelling, multiway cut, integrality gaps, unique games conjecture |
40 | Michael Elkin, David Peleg |
The Hardness of Approximating Spanner Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 41(4), pp. 691-729, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
40 | Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang |
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pp. 226-244, 2005, IEEE Computer Society, 0-7695-2468-0. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
40 | Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
On the Complexity of Hardness Amplification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pp. 170-182, 2005, IEEE Computer Society, 0-7695-2364-1. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
40 | Joseph Cheriyan, Mohammad R. Salavatipour |
Hardness and Approximation Results for Packing Steiner Trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESA ![In: Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pp. 180-191, 2004, Springer, 3-540-23025-4. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
40 | Michael Elkin, David Peleg |
The Hardness of Approximating Spanner Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings, pp. 370-381, 2000, Springer, 3-540-67141-2. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
39 | Julia Chuzhoy, Sanjeev Khanna |
Polynomial flow-cut gaps and hardness of directed cut problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 56(2), pp. 6:1-6:28, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
Directed multicut, hardness of approximation, sparsest cut |
39 | Ishay Haviv, Oded Regev 0001 |
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 469-477, 2007, ACM, 978-1-59593-631-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
lattices, hardness of approximation, tensor product |
39 | Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar |
Hardness of routing with congestion in directed graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 165-178, 2007, ACM, 978-1-59593-631-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
all-or-nothing flow, hardness of approximation, multicommodity flow, edge-disjoint paths, integrality gap, congestion minimization |
39 | Julia Chuzhoy, Sanjeev Khanna |
Polynomial flow-cut gaps and hardness of directed cut problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 179-188, 2007, ACM, 978-1-59593-631-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow |
39 | Irit Dinur, Elchanan Mossel, Oded Regev 0001 |
Conditional hardness for approximate coloring. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 344-353, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
graph coloring, hardness of approximation, unique games conjecture |
39 | Venkatesan Guruswami, Valentine Kabanets |
Hardness Amplification Via Space-Efficient Direct Products. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LATIN ![In: LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings, pp. 556-568, 2006, Springer, 3-540-32755-X. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
error-correcting codes, expanders, Direct products, hardness amplification |
39 | Subhash Khot |
Hardness of approximating the shortest vector problem in lattices. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 52(5), pp. 789-808, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
Approximation algorithms, cryptography, lattices, hardness of approximation, shortest vector problem |
39 | Julia Chuzhoy, Joseph Naor |
New hardness results for congestion minimization and machine scheduling. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 28-34, 2004, ACM, 1-58113-852-0. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
routing, approximation algorithms, hardness of approximation, machine scheduling, congestion minimization |
39 | Surajit Chaudhuri, Mayur Datar, Vivek R. Narasayya |
Index Selection for Databases: A Hardness Study and a Principled Heuristic Solution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEEE Trans. Knowl. Data Eng. ![In: IEEE Trans. Knowl. Data Eng. 16(11), pp. 1313-1323, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
Index selection, hardness result, scalability, linear programming, approximation, NP-hardness, knapsack |
39 | Jacobo Torán |
On the Hardness of Graph Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pp. 180-186, 2000, IEEE Computer Society, 0-7695-0850-2. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
logarithmic space many-one reductions, probabilistic logarithmic space, hardness results, randomized logarithmic space reduction, computational complexity, graph theory, encoding, determinant, graph isomorphism, perfect matching, complexity classes, hardness |
39 | Venkatesan Guruswami, Johan Håstad, Madhu Sudan 0001 |
Hardness of Approximate Hypergraph Coloring. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pp. 149-158, 2000, IEEE Computer Society, 0-7695-0850-2. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
approximate hypergraph coloring, covering complexity, probabilistic verifier, PCP verifier, 2-colorable 4-uniform hypergraph, hardness assumption, computational complexity, computational geometry, minimisation, graph colouring, hardness, minimization problems |
37 | Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim |
Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 24th International Colloquium, ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings, pp. 177-187, 1997, Springer, 3-540-63165-8. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
36 | Deeparnab Chakrabarty, Gagan Goel |
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pp. 687-696, 2008, IEEE Computer Society, 978-0-7695-3436-7. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
36 | Michael Alekhnovich |
More on Average Case vs Approximation Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pp. 298-307, 2003, IEEE Computer Society, 0-7695-2040-5. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
36 | Klaus Ambos-Spies |
Measure Theoretic Completeness Notions for the Exponential Time Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings, pp. 152-161, 2000, Springer, 3-540-67901-4. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
36 | Venkatesan Guruswami |
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX ![In: Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pp. 155-166, 2000, Springer, 3-540-67996-0. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
35 | Andy Rupp, Gregor Leander, Endre Bangerter, Alexander W. Dent, Ahmad-Reza Sadeghi |
Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ASIACRYPT ![In: Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings, pp. 489-505, 2008, Springer, 978-3-540-89254-0. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Generic Group Model, Hardness Conditions, Lower Bounds, Straight-Line Programs |
35 | Wouter M. Bergmann Tiest, Astrid M. L. Kappers |
Kinaesthetic and Cutaneous Contributions to the Perception of Compressibility. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EuroHaptics ![In: Haptics: Perception, Devices and Scenarios, 6th International Conference, EuroHaptics 2008, Madrid, Spain, June 10-13, 2008, Proceedings, pp. 255-264, 2008, Springer, 978-3-540-69056-6. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Softness, Weber fraction, Compliance, Hardness |
35 | Armen P. Sarvazyan, Andrei R. Skovoroda, Yuri P. Pyt'ev |
Mechanical Introscopy -- A New Modality of Medical Imaging for Detection of Breast and Prostate Cancer. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CBMS ![In: Eighth Annual IEEE Symposium on Computer-Based Medical Systems (CBMS'95), June 9-10, 1995, Lubbock, Texas, USA, pp. 4-5, 1995, IEEE Computer Society, 0-8186-7117-3. The full citation details ...](Pics/full.jpeg) |
1995 |
DBLP DOI BibTeX RDF |
stress-strain relations, mechanical introscopy, medical imaging modality, breast cancer detection, prostate cancer detection, soft body tissues internal structure reconstruction, mechanical stress/strain pattern surface distribution, pressure sensor array, elasticity modulus, internal lesions, lesion hardness, mathematical simulation, mass cancer screening method, safety, medical image processing, geometry, inverse problem, biomechanics, elasticity, hardness, pressure sensors, mechanical properties |
33 | Peng Zhang 0008, Jin-yi Cai, Linqing Tang, Wenbo Zhao 0001 |
Approximation and Hardness Results for Label Cut and Related Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TAMC ![In: Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings, pp. 460-469, 2009, Springer, 978-3-642-02016-2. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
33 | Yan Gérard |
About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IWCIA ![In: Combinatorial Image Analysis, 13th International Workshop, IWCIA 2009, Playa del Carmen, Mexico, November 24-27, 2009. Proceedings, pp. 289-301, 2009, Springer, 978-3-642-10208-0. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
Flow problems, NP-complete, Timetable, Discrete Tomography |
33 | Hanafiah B. Yussof, Masahiro Ohka, Jumpei Takata, Yasuo Nasu, Mitsuhiro Yamano |
Low force control scheme for object hardness distinction in robot manipulation based on tactile sensing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICRA ![In: 2008 IEEE International Conference on Robotics and Automation, ICRA 2008, May 19-23, 2008, Pasadena, California, USA, pp. 3443-3448, 2008, IEEE. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
33 | Marcelo Luis Errecalde, Diego Ingaramo, Paolo Rosso |
Proximity Estimation and Hardness of Short-Text Corpora. ![Search on Bibsonomy](Pics/bibsonomy.png) |
DEXA Workshops ![In: 19th International Workshop on Database and Expert Systems Applications (DEXA 2008), 1-5 September 2008, Turin, Italy, pp. 15-19, 2008, IEEE Computer Society, 978-0-7695-3299-8. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
short-text corpora, proximity estimation, cluster validity measures, clustering |
33 | Parikshit Gopalan, Subhash Khot, Rishi Saket |
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 349-359, 2007, IEEE Computer Society, 978-0-7695-3010-9. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
33 | David Pinto 0001, Paolo Rosso |
On the Relative Hardness of Clustering Corpora. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TSD ![In: Text, Speech and Dialogue, 10th International Conference, TSD 2007, Pilsen, Czech Republic, September 3-7, 2007, Proceedings, pp. 155-161, 2007, Springer, 978-3-540-74627-0. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
33 | Venkatesan Guruswami, Prasad Raghavendra |
Hardness of Learning Halfspaces with Noise. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 543-552, 2006, IEEE Computer Society, 0-7695-2720-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
33 | Miroslav Chlebík, Janka Chlebíková |
Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 267-276, 2005, SIAM, 0-89871-585-7. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP BibTeX RDF |
|
33 | Ju Yong Lee, Eunseuk Oh, Hongsik Choi |
Hardness on IP-subnet Aware Routing in WDM Network. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICOIN ![In: Information Networking, Convergence in Broadband and Mobile Networking, International Conference, ICOIN 2005, Jeju Island, Korea, January 31- February 2, 2005, Proceedings, pp. 541-550, 2005, Springer, 3-540-24467-0. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
33 | Subhash Khot |
Hardness of Approximating the Shortest Vector Problem in Lattices. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pp. 126-135, 2004, IEEE Computer Society, 0-7695-2228-9. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
33 | Philipp Kostuch, Krzysztof Socha |
Hardness Prediction for the University Course Timetabling Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EvoCOP ![In: Evolutionary Computation in Combinatorial Optimization, 4th European Conference, EvoCOP 2004, Coimbra, Portugal, April 5-7, 2004, Proceedings, pp. 135-144, 2004, Springer, 3-540-21367-8. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
33 | George Boukeas, Constantinos Halatsis, Vassilis Zissimopoulos, Panagiotis Stamatopoulos |
Measures of Intrinsic Hardness for Constraint Satisfaction Problem Instances. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SOFSEM ![In: SOFSEM 2004: Theory and Practice of Computer Science, 30th Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 24-30, 2004, pp. 184-195, 2004, Springer, 3-540-20779-1. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
33 | Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma |
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comput. Complex. ![In: Comput. Complex. 12(3-4), pp. 85-130, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000). 68Q15 |
33 | Haipeng Guo, William H. Hsu |
GA-Hardness Revisited. ![Search on Bibsonomy](Pics/bibsonomy.png) |
GECCO ![In: Genetic and Evolutionary Computation - GECCO 2003, Genetic and Evolutionary Computation Conference, Chicago, IL, USA, July 12-16, 2003. Proceedings, Part II, pp. 1584-1585, 2003, Springer, 3-540-40603-4. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
33 | Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham |
Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CP ![In: Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, pp. 556-572, 2002, Springer, 3-540-44120-4. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
32 | Gabjong Han, Seokhee Jeon, Seungmoon Choi |
Improving perceived hardness of haptic rendering via stiffness shifting: an initial study. ![Search on Bibsonomy](Pics/bibsonomy.png) |
VRST ![In: Proceedings of the ACM Symposium on Virtual Reality Software and Technology, VRST 2009, Kyoto, Japan, November 18-20, 2009, pp. 87-90, 2009, ACM, 978-1-60558-869-8. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
hardness perception, haptic rendering, stiffness |
32 | Ryan O'Donnell, Yi Wu 0002 |
Conditional hardness for satisfiable 3-CSPs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pp. 493-502, 2009, ACM, 978-1-60558-506-2. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
khot's, satisfiable 3-CSPs, hardness of approximation, PCP |
32 | Zeev Dvir, Amir Shpilka, Amir Yehudayoff |
Hardness-randomness tradeoffs for bounded depth arithmetic circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 741-748, 2008, ACM, 978-1-60558-047-0. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds, arithmetic circuits |
32 | Parikshit Gopalan, Venkatesan Guruswami |
Hardness Amplification within NP against Deterministic Algorithms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 19-30, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Hardness Amplication, Error-Correcting Codes, Derandomization, NP |
32 | Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster |
Approximation algorithms and hardness results for cycle packing problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Algorithms ![In: ACM Trans. Algorithms 3(4), pp. 48, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap |
32 | Refael Hassin, Jérôme Monnot, Danny Segev |
Approximation algorithms and hardness results for labeled connectivity problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 14(4), pp. 437-453, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
Labeled connectivity, Approximation algorithms, Hardness of approximation |
32 | Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet |
Extending the Hardness of RNA Secondary Structure Comparison. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESCAPE ![In: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers, pp. 140-151, 2007, Springer, 978-3-540-74449-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
arc-annotated sequences, NP-hardness, computational biology, edit distance, RNA structures |
32 | Hans Raj Tiwary |
On the hardness of minkowski addition and related operations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SCG ![In: Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pp. 306-309, 2007, ACM, 978-1-59593-705-6. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
coNP-hardness, extended convex hull, polytope intersection, computational geometry, polytopes, turing reduction, minkowski addition |
32 | Julia Chuzhoy, Joseph Naor |
New hardness results for congestion minimization and machine scheduling. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 53(5), pp. 707-721, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
resource minimization, scheduling, network routing, Hardness of approximation, congestion minimization |
32 | Matthew Andrews, Lisa Zhang |
Logarithmic hardness of the undirected edge-disjoint paths problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 53(5), pp. 745-761, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
Hardness of approximation, undirected graphs, edge-disjoint paths |
32 | Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia |
On the computational hardness based on linear FPT-reductions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 11(2), pp. 231-247, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
FPT-reduction, Complexity, Linear, Hardness |
32 | Vitaly Feldman |
Hardness of approximate two-level logic minimization and PAC learning with membership queries. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 363-372, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
DNF minimization, proper learning, two-level logic minimization, hardness of approximation, uniform distribution, membership queries, truth table |
32 | Ramkumar Chinchani, Duc T. Ha, Anusha Iyer, Hung Q. Ngo 0001, Shambhu J. Upadhyaya |
On the Hardness of Approximating the Min-Hack Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 9(3), pp. 295-311, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
hardness of threat analysis, computer security |
32 | Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco |
Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIROCCO ![In: Structural Information and Communication Complexity, 12th International Colloquium, SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings, pp. 200-215, 2005, Springer, 3-540-26052-8. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
black hole search, approximation algorithm, mobile agent, NP-hardness, graph exploration |
32 | Matthew Andrews, Lisa Zhang |
Hardness of the undirected edge-disjoint paths problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 276-283, 2005, ACM, 1-58113-960-8. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
hardness of approximation, undirected graphs, edge-disjoint paths |
32 | Uriel Feige, Shafi Goldwasser, László Lovász 0001, Shmuel Safra, Mario Szegedy |
Interactive Proofs and the Hardness of Approximating Cliques. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 43(2), pp. 268-292, 1996. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
independent set in a graph, multilinearity testing np-completeness, hardness of approximation, probabilistically checkable proofs |
29 | Iftach Haitner |
Semi-honest to Malicious Oblivious Transfer - The Black-Box Way. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TCC ![In: Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008., pp. 412-426, 2008, Springer, 978-3-540-78523-1. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
29 | Vadim Lyubashevsky |
Lattice-Based Identification Schemes Secure Under Active Attacks. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Public Key Cryptography ![In: Public Key Cryptography - PKC 2008, 11th International Workshop on Practice and Theory in Public-Key Cryptography, Barcelona, Spain, March 9-12, 2008. Proceedings, pp. 162-179, 2008, Springer, 978-3-540-78439-5. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
29 | Antoine Joux, Kim Nguyen |
Separating Decision Diffie-Hellman from Computational Diffie-Hellman in Cryptographic Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Cryptol. ![In: J. Cryptol. 16(4), pp. 239-247, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
Elliptic curve, Discrete logarithm, Diffie-Hellman, Weil pairing |
29 | Lane A. Hemaspaandra, Jörg Rothe |
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998, Proceedings, pp. 418-426, 1998, Springer, 3-540-64827-5. The full citation details ...](Pics/full.jpeg) |
1998 |
DBLP DOI BibTeX RDF |
|
29 | Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi |
Hierarchical Specified Unit Disk Graphs (Extended Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993, Proceedings, pp. 21-32, 1993, Springer, 3-540-57899-4. The full citation details ...](Pics/full.jpeg) |
1993 |
DBLP DOI BibTeX RDF |
|
28 | Oded Regev 0001 |
On lattices, learning with errors, random linear codes, and cryptography. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 56(6), pp. 34:1-34:40, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
average-case hardness, cryptography, quantum computation, Lattice, public key encryption |
28 | Wei-Lin Li, Peng Zhang 0008, Daming Zhu |
On Constrained Facility Location Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Sci. Technol. ![In: J. Comput. Sci. Technol. 23(5), pp. 740-748, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
approximation hardness, approximation algorithm, local search, Facility Location |
28 | Mark Burgin |
Universality, Reducibility, and Completeness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MCU ![In: Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orléans, France, September 10-13, 2007, Proceedings, pp. 24-38, 2007, Springer, 978-3-540-74592-1. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
problem completeness, algorithm, computability, reducibility, universal, computing power, problem hardness |
28 | Jonas Holmerin, Subhash Khot |
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 11-20, 2004, ACM, 1-58113-852-0. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
max-bisection, hardness of approximation, linear equations, PCPs |
28 | Patricia A. Evans, Andrew D. Smith |
Complexity of Approximating Closest Substring Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FCT ![In: Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings, pp. 210-221, 2003, Springer, 3-540-40543-7. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
Closest Substring, Approximation algorithms, Hardness of approximation |
28 | Marcus Schaefer 0001, Frank Stephan 0001 |
Strong Reductions and Immunity for Exponential Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, pp. 559-570, 2003, Springer, 3-540-00623-0. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
hardness for exponential time, polynomial time reducibilities, Computational and structural complexity |
28 | Eran Halperin, Robert Krauthgamer |
Polylogarithmic inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pp. 585-594, 2003, ACM, 1-58113-674-9. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
integrality ratio, polylogarithmic approximation, approximation algorithms, Steiner tree, hardness of approximation |
28 | Subhash Khot |
On the Power of Unique 2-Prover 1-Round Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 25, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
2-prover games, Hardness of approximation, probabilistically checkable proofs |
28 | Ian Agol, Joel Hass, William P. Thurston |
3-MANIFOLD KNOT GENUS is NP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 24, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
2-prover games, Hardness of approximation, probabilistically checkable proofs |
28 | Christopher Umans |
Pseudo-Random Generators for All Hardnesses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 11, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
low-degree extension, hardness vs. randomness tradeoffs, pseudo-random generator |
Displaying result #1 - #100 of 4049 (100 per page; Change: ) Pages: [ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][ 10][ >>] |
|