Uriel Feige
From MaRDI portal
List of research outcomes
This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!
| Publication | Date of Publication | Type |
|---|---|---|
| Graphs with tiny vector chromatic numbers and huge chromatic numbers | 2026-05-29 | Paper |
| Witnesses for non-satisfiability of dense random 3CNF formulas | 2026-05-29 | Paper |
| Approximation algorithms for allocation problems: improving the factor of 1 - 1/e | 2026-05-29 | Paper |
| A polylogarithmic approximation of the minimum bisection | 2026-05-08 | Paper |
| Noncryptographic selection protocols | 2026-05-06 | Paper |
| How to hide a clique? | 2026-03-18 | Paper |
| Heuristics for finding large independent sets, with applications to coloring semi-random graphs | 2025-10-29 | Paper |
| Fair shares: feasibility, domination, and incentives Mathematics of Operations Research | 2025-09-30 | Paper |
| Chasing ghosts: competing with stateful policies | 2025-08-05 | Paper |
| The query complexity of searching trees with permanently noisy advice ACM Transactions on Algorithms | 2025-07-22 | Paper |
| Fair-share allocations for agents with arbitrary entitlements Mathematics of Operations Research | 2025-01-28 | Paper |
| How to hide a clique? Theory of Computing Systems | 2024-10-07 | Paper |
| On the path partition number of 6‐regular graphs Journal of Graph Theory | 2023-10-05 | Paper |
| On best-of-both-worlds fair-share allocations Web and Internet Economics | 2023-08-04 | Paper |
| scientific article; zbMATH DE number 7650074 (Why is no real title available?) | 2023-02-03 | Paper |
| A tight negative example for MMS fair allocations (available as arXiv preprint) | 2022-07-06 | Paper |
| Max-min greedy matching Theory of Computing | 2022-05-18 | Paper |
| Navigating in Trees with Permanently Noisy Advice ACM Transactions on Algorithms | 2022-02-16 | Paper |
| Introduction to Semirandom Models | 2022-02-04 | Paper |
| Target set selection for conservative populations Discrete Applied Mathematics | 2021-10-21 | Paper |
| On the probe complexity of local computation algorithms (available as arXiv preprint) | 2021-07-28 | Paper |
| Networks on which hot-potato routing does not livelock Distributed Computing | 2020-12-03 | Paper |
| Shotgun assembly of random jigsaw puzzles Random Structures & Algorithms | 2020-10-26 | Paper |
| Tighter bounds for online bipartite matching Bolyai Society Mathematical Studies | 2020-07-08 | Paper |
| A new approach to fair distribution of welfare (available as arXiv preprint) | 2020-06-30 | Paper |
| Finding cliques using few probes Random Structures & Algorithms | 2020-06-19 | Paper |
| On the profile of multiplicities of complete subgraphs SIAM Journal on Discrete Mathematics | 2020-04-07 | Paper |
| Approximate modularity revisited SIAM Journal on Computing | 2020-01-28 | Paper |
| A polynomial time constant approximation for minimizing total weighted flow-time Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
| On the power of two, three and four probes | 2019-05-06 | Paper |
| On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm | 2019-05-06 | Paper |
| On the cost of recomputing: tight bounds on pebbling with faults Automata, Languages and Programming | 2019-04-29 | Paper |
| A fast randomized LOGSPACE algorithm for graph connectivity Automata, Languages and Programming | 2019-04-29 | Paper |
| scientific article; zbMATH DE number 7014202 (Why is no real title available?) | 2019-02-06 | Paper |
| The ordered covering problem Algorithmica | 2018-07-26 | Paper |
| Random walks with the minimum degree local rule have O(n^2) cover time SIAM Journal on Computing | 2018-07-19 | Paper |
| Random walks with the minimum degree local rule have O(N^2) cover time Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Oblivious rounding and the integrality gap | 2018-04-19 | Paper |
| Contagious sets in random graphs The Annals of Applied Probability | 2018-01-04 | Paper |
| Contagious sets in random graphs The Annals of Applied Probability | 2018-01-04 | Paper |
| Contagious sets in expanders Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| On the effect of randomness on planted 3-coloring models Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| A greedy approximation algorithm for minimum-gap scheduling Journal of Scheduling | 2017-09-01 | Paper |
| Approximate modularity revisited Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
| Invitation games and the price of stability Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
| Why are images smooth? Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
| Separation between estimation and approximation Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
| Welfare maximization and the supermodular degree Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
| Optimization with uniform size queries Algorithmica | 2017-05-11 | Paper |
| Chasing Ghosts: Competing with Stateful Policies SIAM Journal on Computing | 2017-03-10 | Paper |
| Finding hidden cliques in linear time | 2017-02-10 | Paper |
| Nonmonotonic phenomena in packet routing Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
| Two prover protocols, low error at affordable rates Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
| A minimal model for secure computation (extended abstract) Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
| Finding OR in a noisy broadcast network Information Processing Letters | 2016-06-16 | Paper |
| On giant components and treewidth in the layers model Random Structures & Algorithms | 2016-06-10 | Paper |
| Oblivious algorithms for the maximum directed cut problem Algorithmica | 2015-05-26 | Paper |
| Short random walks on graphs Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
| On the integrality ratio of semidefinite relaxations of MAX CUT Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
| Recoverable values for independent sets Random Structures & Algorithms | 2015-02-20 | Paper |
| On fair division of a homogeneous good Games and Economic Behavior | 2015-01-14 | Paper |
| Musical Chairs SIAM Journal on Discrete Mathematics | 2014-12-22 | Paper |
| On maximizing welfare when utility functions are subadditive Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
| Finding small balanced separators Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
| Complete convergence of message passing algorithms for some satisfiability problems Theory of Computing | 2014-10-06 | Paper |
| Approximating the domatic number Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
| Approximating the minimum bisection size (extended abstract) Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
| Santa claus meets hypergraph matchings ACM Transactions on Algorithms | 2014-09-09 | Paper |
| Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
| Min-Max Graph Partitioning and Small Set Expansion SIAM Journal on Computing | 2014-07-30 | Paper |
| Min-Max Graph Partitioning and Small Set Expansion SIAM Journal on Computing | 2014-07-30 | Paper |
| Min-max Graph Partitioning and Small Set Expansion 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
| Demand Queries with Preprocessing Automata, Languages, and Programming | 2014-07-01 | Paper |
| Mechanism design with uncertain inputs, (to err is human, to forgive divine) Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Short Tours through Large Linear Forests Integer Programming and Combinatorial Optimization | 2014-06-02 | Paper |
| On robustly asymmetric graphs | 2014-02-05 | Paper |
| Connectivity of random high dimensional geometric graphs Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
| Universal factor graphs Automata, Languages, and Programming | 2013-08-12 | Paper |
| A greedy approximation algorithm for minimum-gap scheduling Lecture Notes in Computer Science | 2013-06-07 | Paper |
| PASS approximation: a framework for analyzing and designing heuristics Algorithmica | 2013-05-13 | Paper |
| Buffer management for colored packets with deadlines Theory of Computing Systems | 2012-12-10 | Paper |
| On estimation algorithms vs approximation algorithms | 2012-10-19 | Paper |
| Maximizing Non-monotone Submodular Functions SIAM Journal on Computing | 2011-11-07 | Paper |
| Oblivious Collaboration Lecture Notes in Computer Science | 2011-10-28 | Paper |
| On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas SIAM Journal on Discrete Mathematics | 2011-10-27 | Paper |
| An O(n n) algorithm for a load balancing problem on paths Lecture Notes in Computer Science | 2011-08-12 | Paper |
| Recoverable values for independent sets Lecture Notes in Computer Science | 2011-07-06 | Paper |
| On optimal strategies for a hat game on graphs SIAM Journal on Discrete Mathematics | 2011-06-17 | Paper |
| scientific article; zbMATH DE number 5899254 (Why is no real title available?) Theory of Computing | 2011-05-24 | Paper |
| The submodular welfare problem with demand queries Theory of Computing | 2011-05-24 | Paper |
| Hardness results for approximating the bandwidth Journal of Computer and System Sciences | 2011-01-18 | Paper |
| Balanced coloring of bipartite graphs Journal of Graph Theory | 2010-11-24 | Paper |
| A direct reduction from k-player to 2-player approximate Nash equilibrium Algorithmic Game Theory | 2010-10-19 | Paper |
| Responsive lotteries Algorithmic Game Theory | 2010-10-19 | Paper |
| Improved approximation algorithms for minimum-weight vertex separators Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
| Combination can be hard Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
| On sums of independent random variables with unbounded variance, and estimating the average degree in a graph Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
| scientific article; zbMATH DE number 5764883 (Why is no real title available?) | 2010-08-06 | Paper |
| Relations between average case complexity and approximation complexity Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
| A preemptive algorithm for maximizing disjoint paths on trees Algorithmica | 2010-05-19 | Paper |
| On maximizing welfare when utility functions are subadditive SIAM Journal on Computing | 2010-03-17 | Paper |
| An improved approximation ratio for the minimum linear arrangement problem Information Processing Letters | 2010-01-29 | Paper |
← Previous 100 1 2 Next 100 →
Research outcomes over time
This page was built for person: Uriel Feige
